美文网首页算法学习
算法题--判断二叉树是否左右对称

算法题--判断二叉树是否左右对称

作者: 岁月如歌2020 | 来源:发表于2020-04-28 12:38 被阅读0次
image.png

0. 链接

题目链接

1. 题目

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

    1
   / \
  2   2
   \   \
   3    3

Follow up: Solve it both recursively and iteratively.

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指向其右子节点
            
  1. 分别用cur_2cur_2跟踪两棵子树, 一个正向中序遍历,一个反向中序遍历, 在任一步骤上不一致, 均中途退出,返回失败;
  2. 遍历完毕后, 判断是否仍有一方的指针指向非空节点, 如果出现,也返回失败.
  3. 返回成功

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 Solution1:
    def isSymmetric(self, root: TreeNode) -> bool:

        def check(root1, root2):
            cur_1 = root1
            cur_2 = root2

            rtn = True
            while cur_1 is not None and cur_2 is not None:
                if cur_1.left is None and cur_2.right is None:
                    if cur_1.val != cur_2.val:
                        rtn = False
                        break
                    cur_1 = cur_1.right
                    cur_2 = cur_2.left
                elif cur_1.left is not None and cur_2.right is not None:
                    pre_1 = cur_1.left
                    pre_2 = cur_2.right
                    while pre_1.right is not None and pre_1.right != cur_1:
                        pre_1 = pre_1.right
                    while pre_2.left is not None and pre_2.left != cur_2:
                        pre_2 = pre_2.left
                    if pre_1.right is None and pre_2.left is None:
                        pre_1.right = cur_1
                        pre_2.left = cur_2
                        cur_1 = cur_1.left
                        cur_2 = cur_2.right
                    elif pre_1.right is not None and pre_2.left is not None:
                        pre_1.right = None
                        pre_2.left = None
                        if cur_1.val != cur_2.val:
                            rtn = False
                            break
                        cur_1 = cur_1.right
                        cur_2 = cur_2.left
                    else:
                        rtn = False
                        break
                else:
                    rtn = False
                    break

            cur_1_is_none = (cur_1 is None)
            cur_2_is_none = (cur_2 is None)
            if cur_1_is_none ^ cur_2_is_none:
                rtn = False

            return rtn

        return check(root.left, root.right) if root is not None else True


solution = Solution1()

root1 = node = TreeNode(1)
node.left = TreeNode(2)
node.right = TreeNode(2)
node.left.left = TreeNode(3)
node.left.right = TreeNode(4)
node.right.left = TreeNode(4)
node.right.right = TreeNode(3)
node.left.left.left = TreeNode(5)
node.left.left.right = TreeNode(6)
node.left.right.left = TreeNode(7)
node.left.right.right = TreeNode(8)
node.right.left.left = TreeNode(8)
node.right.left.right = TreeNode(7)
node.right.right.left = TreeNode(6)
node.right.right.right = TreeNode(5)

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

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

root4 = node = TreeNode(1)
node.left = TreeNode(2)
node.right = TreeNode(2)
node.left.left = TreeNode(3)
node.left.right = TreeNode(4)
node.right.left = TreeNode(4)
node.right.right = TreeNode(3)

print(solution.isSymmetric(root1))
print(solution.isSymmetric(root2))
print(solution.isSymmetric(root3))
print(solution.isSymmetric(root4))



输出结果

True
False
False
True

4. 结果

image.png

5. 思路2: 递归

特别简单,都不想介绍了,哈哈:)

大概就是判断left和right的值是否同时为None或者同时为非None,如若不然,直接失败

然后判断left和right的值相等 且 <left.right, right.left>, <left.left, right.right> 是否也满足相等关系(通过递归调用来实现)

6. 代码

# 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 isSymmetric(self, root: TreeNode) -> bool:

        def check(left, right):
            left_is_none = (left is None)
            right_is_none = (right is None)
            if left_is_none ^ right_is_none:
                return False
            if left_is_none and right_is_none:
                return True

            return left.val == right.val \
                   and check(left.left, right.right) \
                   and check(left.right, right.left)

        return check(root.left, root.right) if root is not None else True


solution = Solution()

root1 = node = TreeNode(1)
node.left = TreeNode(2)
node.right = TreeNode(2)
node.left.left = TreeNode(3)
node.left.right = TreeNode(4)
node.right.left = TreeNode(4)
node.right.right = TreeNode(3)
node.left.left.left = TreeNode(5)
node.left.left.right = TreeNode(6)
node.left.right.left = TreeNode(7)
node.left.right.right = TreeNode(8)
node.right.left.left = TreeNode(8)
node.right.left.right = TreeNode(7)
node.right.right.left = TreeNode(6)
node.right.right.right = TreeNode(5)

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

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

root4 = node = TreeNode(1)
node.left = TreeNode(2)
node.right = TreeNode(2)
node.left.left = TreeNode(3)
node.left.right = TreeNode(4)
node.right.left = TreeNode(4)
node.right.right = TreeNode(3)

print(solution.isSymmetric(root1))
print(solution.isSymmetric(root2))
print(solution.isSymmetric(root3))
print(solution.isSymmetric(root4))

输出结果

True
False
False
True

7. 结果

image.png

相关文章

  • 算法题--判断二叉树是否左右对称

    0. 链接 题目链接 1. 题目 Given a binary tree, check whether it is...

  • Leetcode.101.Symmetric Tree

    题目 给定一个二叉树, 判断这个二叉树是否对称. 思路 判断这个数是否对称: 将根节点的右边子树所有左右节点都交换...

  • 二叉树--自对称判断

    今天学习的算法是判断二叉树是否自对称。 题目介绍 对称二叉树的特点是将跟节点的左右子树翻转后,树与原来保持完全一致...

  • [LeetCode OJ]- SymmetricTree

    题目要求:判断一颗二叉树是否为左右对称的。这里的左右对称不仅要求结构上左右对称,而且节点的值也应该满足左右对称。 ...

  • 面试题28:对称二叉树

    判断一颗二叉树是不是对称二叉树 思路:该题的思路为与上一题相似,递归判断左右子树。

  • 101. Symmetric Tree

    判断二叉树是否对称 同时遍历左子树和右子树,判断是否对称

  • LeetCode 力扣 101. 对称二叉树

    题目描述(简单难度) 判断一个二叉树是否关于中心轴对称。 解法一 和 100 题 判断两个二叉树是否相等其实是一样...

  • 关于二叉树的算法题

    前序遍历中序遍历后序遍历判断是否是平衡二叉树判断是否是对称二叉树判断二叉树高度按照层遍历二叉树判断二叉树宽度

  • 【剑指offer】问题28:对称的二叉树

    判断一棵二叉树是否是对称二叉树。对称二叉树的定义就是左子树跟右子树是反着的。 也是一道递归的题目,跟27题差不太多...

  • 算法题解:判断链表是否为回文链表

    大家好,我是前端西瓜哥,今天来做一道算法题。 给一个单链表,判断是否为回文链表。 所谓回文,就是左右值对称相同的链...

网友评论

    本文标题:算法题--判断二叉树是否左右对称

    本文链接:https://www.haomeiwen.com/subject/jqjvwhtx.html