LeetCode 100. 相同的树（易）

关于两颗树是否相同的判定，直接进行前序遍历，如果遍历结果一样，说明是同一棵树。

题目

给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例

示例 1:

1
2
3
4
5
6
7
输入:       1         1
          / \       / \
         2   3     2   3

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

输出: true

示例 2:

1
2
3
4
5
6
7
输入:      1          1
          /           \
         2             2

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

输出: false

示例 3:

1
2
3
4
5
6
7
输入:       1         1
          / \       / \
         2   1     1   2

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

输出: false

考察知识点

二叉树

核心思想

直觉
进行前序遍历，如果遍历结果一样，说明是同一棵树。

Python版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        # 进行前序遍历，如果遍历结果一样，说明是同一棵树。
        p_res = self.PreOrder_circulation(p)
        q_res = self.PreOrder_circulation(q)
        return p_res == q_res
    
    # 循环/栈 前序遍历，根结点 ---> 左子树 ---> 右子树。
    def PreOrder_circulation(self, root):
        """
        Pre-Order Traversal of binary tree based on circulation
        :param root: root node of target binary tree
        :return: TreeNode
        """
        res = []
        stack = []
        if root:
            stack.append(root)
            while len(stack):
                node = stack.pop()
                if node == None:
                    res.append(None)
                else:
                    res.append(node.val)
                    stack.append(node.right)  # 再入栈右子树 下一次循环的时候先入后出
                    stack.append(node.left)  # 再入栈左子树 下一次循环的时候后入先出（实现了根 -> 左 -> 右）
        return res