# [leetcode/lintcode 题解]算法面试高频题详解： 对称树

样例1

1
/ \
2   2
/ \ / \
3  4 4  3
{1,2,2,3,4,4,3}这棵二叉树是对称的
样例2

1
/ \
2   2
\   \
3    3

Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None

class Solution:

    @param root: root of the given tree
@return: whether it is a mirror of itself
"""
def isSymmetric(self, root):
if not root:
return True
return self._is_symmetric(root.left, root.right)

def _is_symmetric(self, left_root, right_root):
if left_root is None and right_root is None:
return True
if left_root is None or right_root is None:
return False
if left_root.val != right_root.val:
return False

left = self._is_symmetric(left_root.left, right_root.right)
right = self._is_symmetric(left_root.right, right_root.left)
return left and right

Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None

class Solution:

    @param root: root of the given tree
@return: whether it is a mirror of itself
"""

def isSymmetric(self, root):
inorder = self.inorder(root, reverse=False)
reverse_inorder = self.inorder(root, reverse=True)
if inorder != reverse_inorder:
return False

preorder = self.preorder(root, reverse=False)
reverse_preorder = self.preorder(root, reverse=True)
return preorder == reverse_preorder

def get_left(self, node, reverse):
if reverse:
return node.right
return node.left

def get_right(self, node, reverse):
if reverse:
return node.left
return node.right

def preorder(self, root, reverse):
stack = [root]
order = []
while stack:
node = stack.pop()
order.append(node.val)
right = self.get_right(node, reverse)
if right:
stack.append(right)
left = self.get_left(node, reverse)
if left:
stack.append(left)
return order

def inorder(self, root, reverse):
stack = []
while root is not None:
stack.append(root)
root = self.get_left(root, reverse)

order = []
while stack:
node = stack[-1]
order.append(node.val)
right = self.get_right(node, reverse)
if right is not None:
node = right
while node is not None:
stack.append(node)
node = self.get_left(node, reverse)
else:
stack.pop()
while stack and self.get_right(stack[-1], reverse) == node:
node = stack.pop()

return order

Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None

class Solution:

    @param root: root of the given tree
@return: whether it is a mirror of itself
"""
def isSymmetric(self, root):
queue = [root]
while queue:
next_queue = []
for i in range(len(queue)):
if queue[i] is None:
continue
next_queue.append(queue[i].left)
next_queue.append(queue[i].right)
if not self.is_mirror(next_queue):
return False
queue = next_queue
return True

def is_mirror(self, queue):
left, right = 0, len(queue) - 1
while left < right:
if not self.is_same(queue[left], queue[right]):
return False
left, right = left + 1, right - 1
return True

def is_same(self, node1, node2):
if node1 and node2:
return node1.val == node2.val
return node1 is None and node2 is None

|
1天前
|

Python中的决策树算法探索
Python中的决策树算法探索
12 2
|
2天前
|

11 0
|
7天前
|

29 4
|
8天前
|

20 2
|
8天前
|

11 2
|
9天前
|
SQL 算法 大数据

6 0
|
9天前
|

5 0
|
9天前
|
SQL 大数据 数据挖掘

8 0
|
9天前
|
SQL 算法 大数据

9 1
|
9天前
|

6 0