572. Subtree of Another Tree - Easy

发布时间：2020-12-14 05:18:19 所属栏目：大数据来源：网络整理

导读：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 b

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.

Example 1:
Given tree s:

     3
    /    4   5
  /  1   2

Given tree t:

   4 
  /  1   2

Return?true,because t has the same structure and node values with a subtree of s.

Example 2:
Given tree s:

Given tree t:

   4
  /  1   2

Return?false.

先判断s当前节点的子树和t是否是同一个树；如果不是，递归判断t是否是s.left/s.right的子树；

time: O(n),space: O(logn)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode s,TreeNode t) {
        if(s == null) {
            return false;
        }
        if(isSame(s,t)) {
            return true;
        }
        return isSubtree(s.left,t) || isSubtree(s.right,t);
    }
    
    public boolean isSame(TreeNode s,TreeNode t) {
        if(s == null && t == null) {
            return true;
        }
        if(s == null || t == null) {
            return false;
        }
        if(s.val != t.val) {
            return false;
        }
        return isSame(s.left,t.left) && isSame(s.right,t.right);
    }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!