Algorithm

[LeetCode 572] Subtree of Another Tree [Java] [Beats : 99.94%]

顿搜

2017-09-23

0 评论

674 阅读

正在检测是否收录...

09/23

1. Description

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.

2. Runtime Distribution

3. Submission Details

4. Example

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.

5. Code

public boolean isSubtree(TreeNode s, TreeNode t) {
    if (t == null && s == null) {
        return true;
    } else if (t == null || s == null) {
        return false;
    }
    return isSubtreeRoot(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
}

public boolean isSubtreeRoot(TreeNode s, TreeNode t) {
    if (t == null && s == null) {
        return true;
    } else if (t == null || s == null) {
        return false;
    }
    if (t.val == s.val) {
        return isSubtreeRoot(s.left, t.left) && isSubtree(s.right, t.right);
    }
    return false;
}

6.Test

public class LeetCode0572 {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (t == null && s == null) {
            return true;
        } else if (t == null || s == null) {
            return false;
        }
        return isSubtreeRoot(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
    }

    public boolean isSubtreeRoot(TreeNode s, TreeNode t) {
        if (t == null && s == null) {
            return true;
        } else if (t == null || s == null) {
            return false;
        }
        if (t.val == s.val) {
            return isSubtreeRoot(s.left, t.left) && isSubtree(s.right, t.right);
        }
        return false;
    }
}

Tree

朗读