算法题--判断二叉树是否左右对称
2020-04-28 本文已影响0人
岁月如歌2020
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中序遍历
- 建立螺纹二叉树(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指向其右子节点
- 分别用
cur_2和cur_2跟踪两棵子树, 一个正向中序遍历，一个反向中序遍历， 在任一步骤上不一致, 均中途退出，返回失败; - 遍历完毕后, 判断是否仍有一方的指针指向非空节点, 如果出现，也返回失败.
- 返回成功
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
