算法题--判断两棵二叉树是否一致

image.png

0. 链接

题目链接

1. 题目

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

Input:     1         1
          / \       / \
         2   3     2   3

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

Output: true

Example 2:

Input:     1         1
          /           \
         2             2

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

Output: false

Example 3:

Input:     1         1
          / \       / \
         2   1     1   2

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

Output: false

2. 思路1: Morris中序遍历(递归和栈结构迭代方法实现较为简单, 就懒得写了:))

1. 建立螺纹二叉树(Threaded Binary Tree), 即满足下列两个要求：

• 1.1 所有原本为空的右子节点指向中序遍历顺序之后的那个节点;
• 1.2 所有原本为空的左子节点指向中序遍历顺序之前的那个节点

具体实现过程:

(1) 初始化指针cur指向root
(2) 当cur不为空时
    -- 如果cur没有左子节点, 说明找到了目前未遍历到的部分的最小值，则
        a) 得到一个中序遍历的元素cur.val
        b) 将cur指向其右子节点(可理解为目前未遍历到的最靠左的那个树的右子节点, 变成了最新的最左端)
    -- 否则
        将pre指针指向cur的左子树中的最右子节点, 不能指向cur(目的是实现1.1的要求)
        ** 若pre的右子节点为空, 说明找到了1.1要求的那个节点, 则
            a) 将pre的右子节点指向cur
            b) 将cur指向cur.left
        ** 否则
            a) 将pre的右子节点置空
            b) 得到一个中序遍历的元素cur.val
            c) 将cur指向其右子节点
            

2. 分别用p_cur和q_cur跟踪两棵树, 在任一步骤上不一致, 均中途退出，返回失败;
3. 遍历完毕后, 判断是否仍有一方的指针指向非空节点, 如果出现，也返回失败.
4. 返回成功

3. 代码

# coding:utf8

# 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:
        p_cur = p
        q_cur = q

        rtn = True

        while p_cur is not None and q_cur is not None:
            if p_cur.left is None and q_cur.left is None:
                if p_cur.val != q_cur.val:
                    rtn = False
                    break
                p_cur = p_cur.right
                q_cur = q_cur.right
            elif p_cur.left is not None and q_cur.left is not None:
                p_pre = p_cur.left
                q_pre = q_cur.left
                while p_pre.right is not None and p_pre.right != p_cur:
                    p_pre = p_pre.right
                while q_pre.right is not None and q_pre.right != q_cur:
                    q_pre = q_pre.right
                if p_pre.right is None and q_pre.right is None:
                    p_pre.right = p_cur
                    q_pre.right = q_cur
                    p_cur = p_cur.left
                    q_cur = q_cur.left
                elif p_pre.right is not None and q_pre.right is not None:
                    p_pre.right = None
                    q_pre.right = None
                    if p_cur.val != q_cur.val:
                        rtn = False
                        break
                    p_cur = p_cur.right
                    q_cur = q_cur.right
                else:
                    rtn = False
                    break
            else:
                rtn = False
                break
        
        if p_cur is None and q_cur is not None:
            rtn = False
        if p_cur is not None and q_cur is None:
            rtn = False
            
        return rtn


solution = Solution()

# 第一组
p_1 = node = TreeNode(1)
node.left = TreeNode(2)
node.right = TreeNode(3)

q_1 = node = TreeNode(1)
node.left = TreeNode(2)
node.right = TreeNode(3)

# 第二组
p_2 = node = TreeNode(1)
node.left = TreeNode(2)

q_2 = node = TreeNode(1)
node.right = TreeNode(2)

# 第三组
p_3 = node = TreeNode(1)
node.left = TreeNode(2)
node.right = TreeNode(1)

q_3 = node = TreeNode(1)
node.left = TreeNode(1)
node.right = TreeNode(2)

print(solution.isSameTree(p_1, q_1))
print(solution.isSameTree(p_2, q_2))
print(solution.isSameTree(p_3, q_3))

输出结果

True
False
False

结果

image.png