题解 | #树的子结构#
树的子结构
http://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88
树的子结构
递归解决
public class Solution { public boolean HasSubtree(TreeNode root1,TreeNode root2) { //这个主要是用来定位大树中节点位置的,便于与子树的头节点对应 return (root1 != null && root2 != null) && (recursive(root1,root2) || HasSubtree(root1.left,root2) ||HasSubtree(root1.right , root2)); } //树结构比较 public boolean recursive(TreeNode nodeA, TreeNode nodeB) { //为什么先检查子树是否为空?子树一旦为空,就已经达到了子树的结尾部分,说明在大树中已经找到了完整的该子树 if (nodeB == null) return true; //1、节点nodeA为空时,说明大树中的这个位置点缺失为空,但子树中这个位置却是有的,坑定不能继续往下走了,所以返回 //2、当前节点位置大树和子树的节点值不一样,同样是错误的,需要返回 if (nodeA == null || nodeA.val != nodeB.val) return false; //最后如果当前位置大树和子树的值和结构没问题,继续往下面的节点走,继续检查,直到检查完成 return recursive(nodeA.left, nodeB.left) && recursive(nodeA.right, nodeB.right); } }