本文共 1439 字，大约阅读时间需要 4 分钟。

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.

我的想法

用递归来写。但这样写对于[1,1] [1]这样的corner case会错判为false，因为在根结点发现相等后就已经往下判断结构了。

class Solution {
       public boolean isSubtree(TreeNode s, TreeNode t) {
           if(s == null || t == null) {
               return s == t ? true : false;        }                if(s.val == t.val) {
           	//注意这里是&&保证结构相同            return isSubtree(s.left, t.left) && isSubtree(s.right, t.right);        }        //这里是||只要左右子树有一个满足就为真        return isSubtree(s.left, t) || isSubtree(s.right, t);    }}

解答

看了下答案之后发现，只要把整个函数拆成两个步骤递归即可。第一个递归比较的根结点，第二个递归比较结构是否相同

class Solution {
       public boolean isSubtree(TreeNode s, TreeNode t) {
           if(s == null || t == null) {
               return s == t ? true : false;        }        if(s.val == t.val && compare(s, t)) {
               return true;        }                return isSubtree(s.left, t) || isSubtree(s.right, t);    }    private boolean compare(TreeNode s, TreeNode t) {
           if(s == null || t == null) {
               return s == t ? true : false;        }                if(s.val != t.val) {
               return false;        }        return compare(s.left, t.left) && compare(s.right, t.right);    }}

转载地址：http://xyqvb.baihongyu.com/