#572. Subtree of Another Tree

題目描述

給你兩個二元樹的根節點root和subRoot，如果root存在與subRoot相同結構的子樹與節點值，回傳true，反之回傳false。

子樹是二元樹內的一個節點與它所有的子節點所組成，二元樹的根結點也可以同時是子樹的根結點。

限制條件

1. root的節點數量[1, 2000]。
2. subRoot的節點數量[1, 1000]。
3. -10^4 <= root.val <= 10^4
4. -10^4 <= subRoot.val <= 10^4

解題思路

Traversal

這一題有兩件事情要做，找到子樹的起點和確認結構和值是不是一樣。

public class Solution { 
	public bool IsSubtree(TreeNode root, TreeNode subRoot) {
        if(root==null) return false;
        if(root.val == subRoot.val){                   
            if(PathCheck(root,subRoot)) return true;
        }         
        return IsSubtree(root.left,subRoot) || IsSubtree(root.right,subRoot);
    }
    public bool PathCheck(TreeNode root, TreeNode subRoot){        
        if(root==null && subRoot==null) return true;
        if(root==null || subRoot==null) return false;         
        if(root.val != subRoot.val) return false;        
        return  PathCheck(root.left,subRoot.left) && PathCheck(root.right,subRoot.right);
    }
}

複雜度分析：

• 時間複雜度：最差的情況要檢查所有節點和所有子樹的節點，因此時間複雜度為O(m+n)。
• 空間複雜度：最差的情況所有節點要採完才會收斂，因此空間複雜度為O(m+n)。

學習重點

• Traversal