树的子结构

• 题目描述

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean hasSubtree(TreeNode pRoot1, TreeNode pRoot2) {
        if (pRoot1 == null || pRoot2 == null) { //遇到空节点直接返回false
            return false;
        }
        if (isPart(pRoot1, pRoot2)) { //遍历树A的所有非空节点，判断树A中以R为根的子树是否与树B有一样的结构
            return true;
        }
        return hasSubtree(pRoot1.left, pRoot2) || hasSubtree(pRoot1.right, pRoot2); // 递归遍历A的所有子节点
    }
    
    public boolean isPart(TreeNode p1, TreeNode p2) {
        if (p2 == null) { //树B遍历到了空，说明当前分支匹配，返回true
            return true;
        }
        if (p1 == null || p1.val != p2.val) { //树A为空且树B不为空，或者两个节点都不为空但数值不同，均返回false
            return false;
        }
        return isPart(p1.left, p2.left) && isPart(p1.right, p2.right); // 否则说明当前这个点匹配，递归遍历左子树和右子树
    }
}