树的子结构

Posted on Edited on In Views: Waline: Views: Symbols count in article: 570 Reading time ≈ 1 mins.

题解方法

  • 递归

    递归

  1. 递归判断 A 的当前节点是否包含 B。
  2. 分别递归遍历 A 的左右子树，过程中递归判断当前节点是否包含 B。

    核心代码

    递归

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    public boolean isSubStructure(TreeNode A, TreeNode B) {
    	if (B == null) {
    		return false;
    	}
    	return isContained(A, B) || (A != null && (isSubStructure(A.left, B) || isSubStructure(A.right, B)));
    }

    private boolean isContained(TreeNode A, TreeNode B) {
    	// B 遍历结束，说明 B 是 A 的子结构
    	if (B == null) {
    		return true;
    	}
    	if (A == null) {
    		return false;
    	}
    	if (A.val != B.val) {
    		return false;
    	}
    	return isContained(A.left, B.left) && isContained(A.right, B.right);
    }

    题目来源