Skip to content

Latest commit

 

History

History
159 lines (133 loc) · 6.15 KB

100.md

File metadata and controls

159 lines (133 loc) · 6.15 KB

100. 相同的树

整体思路

  • 两个树相同，中根遍历肯定相同；中根遍历相同，两个树就一定相同？不一定，比如这种情况，中根遍历都是 [1,2]

    输入:      1          1
          /           \
         2             2

  • 如果中根遍历，先根遍历，后根遍历均相同，那肯定是相同的树。但遍历 3 遍，时间复杂度太高。这道题是简单，显然不会这么复杂

  • 中根遍历只记录非空「值」，如果将没有空节点也记录，可以通过判断遍历结果（[1,2,null], [1,null,2]）是否相同来判断两个树是否相同。这是解法一：通过遍历结果是否相同来判断。

  • 通过两个数组是否完全相同来判断，其实也是依次判断每一个元素是否相同，如果都相同，则最终结果相同。依次判断每一个节点是否相同，相同为 true，不同为 false，存在 false，则最后结果为 false。这是解法二

解法一：通过判断遍历结果是否相同

  • 标签：递归、数组
  • 思路转代码：利用递归得到两个树的中根遍历数组，为 null 也加入数组
  • 时间复杂度：O(N)，递归栈的深度为节点的数量（N）
  • 空间复杂度：O(N)，需要一个额外长度为 N 的数组（不考虑叶子节点为 null 的情况）

代码

# Python3
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        pvals,qvals = [],[]
        self.traversal(p, pvals)
        self.traversal(q, qvals)
        return pvals == qvals
        
    def traversal(self, root: TreeNode, vals: List[int]) -> None::
        if root == None:
            return
        vals.append(root.val)
        if root.left != None:
            self.traversal(root.left,vals)
        else:
            vals.append(None)
        if root.right != None:
            self.traversal(root.right,vals)
        else:
            vals.append(None)
// Java
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        List<Integer> pvals = new ArrayList<>();
        List<Integer> qvals = new ArrayList<>();
        traversal(p, pvals);
        traversal(q, qvals);
        return pvals.equals(qvals);
    }
    
    private void traversal(TreeNode root, List<Integer> vals) {
        if (root == null) {
            return;
        }
        vals.add(root.val);
        if (root.left != null) {
            traversal(root.left, vals);
        } else {
            vals.add(null);
        }
        if (root.right != null) {
            traversal(root.right, vals);
        } else {
            vals.add(null);
        }
    }
}

解法二：依次判断每一个节点是否相同

  • 标签：递归
  • 思路转代码：
    1. 先判断是否均为 null，避免获取空节点 val 报错
    2. 再判断是否存在 null，存在 null，说明两者不一样，因为都不会 null
    3. 通过前面两个判断，肯定都不为空，此时判断值是否相等
  • 时间复杂度：O(N)，递归栈的深度为节点的数量（N）
  • 空间复杂度：O(1)，不需要额外的空间

代码

# Python3
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if p == None and q == None:
            return True
        if p == None or q == None:
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
// Java
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

测试用例

[390,255,2266,-273,337,1105,3440,-425,4113,null,null,600,1355,3241,4731,-488,-367,16,null,565,780,1311,1755,3075,3392,4725,4817,null,null,null,null,-187,152,395,null,728,977,1270,null,1611,1786,2991,3175,3286,null,164,null,null,4864,-252,-95,82,null,391,469,638,769,862,1045,1138,null,1460,1663,null,1838,2891,null,null,null,null,3296,3670,4381,null,4905,null,null,null,-58,null,null,null,null,null,null,null,null,734,null,843,958,null,null,null,1163,1445,1533,null,null,null,2111,2792,null,null,null,3493,3933,4302,4488,null,null,null,null,null,null,819,null,null,null,null,1216,null,null,1522,null,1889,2238,2558,2832,null,3519,3848,4090,4165,null,4404,4630,null,null,null,null,null,null,1885,2018,2199,null,2364,2678,null,null,null,3618,3751,null,4006,null,null,4246,null,null,4554,null,null,null,1936,null,null,null,null,2444,2642,2732,null,null,null,null,null,null,null,4253,null,null,null,null,2393,2461,null,null,null,null,4250,null,null,null,null,2537]
[390,255,2266,-273,337,1105,3440,-425,4113,null,null,600,1355,3241,4731,-488,-367,16,null,565,780,1311,1755,3075,3392,4725,4817,null,null,null,null,-187,152,395,null,728,977,1270,null,1611,1786,2991,3175,3286,null,164,null,null,4864,-252,-95,82,null,391,469,638,769,862,1045,1138,null,1460,1663,null,1838,2891,null,null,null,null,3296,3670,4381,null,4905,null,null,null,-58,null,null,null,null,null,null,null,null,734,null,843,958,null,null,null,1163,1445,1533,null,null,null,2111,2792,null,null,null,3493,3933,4302,4488,null,null,null,null,null,null,819,null,null,null,null,1216,null,null,1522,null,1889,2238,2558,2832,null,3519,3848,4090,4165,null,4404,4630,null,null,null,null,null,null,1885,2018,2199,null,2364,2678,null,null,null,3618,3751,null,4006,null,null,4246,null,null,4554,null,null,null,1936,null,null,null,null,2444,2642,2732,null,null,null,null,null,null,null,4253,null,null,null,null,2461,2393,null,null,null,null,4250,null,null,null,null,2537]

[1,2,3]
[1,2,3]

[]
[]

[1,2]
[1,null,2]