二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”

**二叉树系列**

### 一、对称二叉树#### 题目描述给定一个二叉树，判断它是否是对称的。

#### 示例输入：[1,2,2,3,4,4,3]
输出：true输入：[1,2,2,null,3,null,3]
输出：false#### 解决方案

class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef isSymmetric(root):
 """
 :type root: TreeNode :rtype: bool """
 if not root:
 return True def isMirror(t1, t2):
 if not t1 and not t2:
 return True if not t1 or not t2:
 return False return (t1.val == t2.val) and isMirror(t1.right, t2.left) and isMirror(t1.left, t2.right)
 return isMirror(root.left, root.right)

# 测试用例root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(2)
root.left.left = TreeNode(3)
root.left.right = TreeNode(4)
root.right.left = TreeNode(4)
root.right.right = TreeNode(3)

print(isSymmetric(root)) # trueroot = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(2)
root.left.right = TreeNode(3)
root.right.right = TreeNode(3)

print(isSymmetric(root)) # false

class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef isSubtree(T1, T2):
 """
 :type T1: TreeNode :type T2: TreeNode :rtype: bool """
 if not T2:
 return True def isSameTree(t1, t2):
 if not t1 and not t2:
 return True if not t1 or not t2:
 return False return (t1.val == t2.val) and isSameTree(t1.right, t2.right) and isSameTree(t1.left, t2.left)
 for node in T1:
 if isSameTree(node, T2):
 return True return False# 测试用例root1 = TreeNode(3)
root1.left = TreeNode(9)
root1.right = TreeNode(20)
root1.right.left = TreeNode(15)
root1.right.right = TreeNode(7)

root2 = TreeNode(3)
root2.left = TreeNode(9)
root2.right = TreeNode(20)

print(isSubtree(root1, root2)) # trueroot2 = TreeNode(3)
root2.left = TreeNode(9)
root2.right = TreeNode(15)
root2.right.right = TreeNode(7)

print(isSubtree(root1, root2)) # false

class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef preorderTraversal(root):
 """
 :type root: TreeNode :rtype: List[int]
 """
 if not root:
 return []
 result = [root.val]
 result += preorderTraversal(root.left)
 result += preorderTraversal(root.right)
 return resultdef inorderTraversal(root):
 """
 :type root: TreeNode :rtype: List[int]
 """
 if not root:
 return []
 result = []
 result += inorderTraversal(root.left)
 result.append(root.val)
 result += inorderTraversal(root.right)
 return resultdef postorderTraversal(root):
 """
 :type root: TreeNode :rtype: List[int]
 """
 if not root:
 return []
 result = []
 result += postorderTraversal(root.left)
 result += postorderTraversal(root.right)
 result.append(root.val)
 return result# 测试用例root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

print(preorderTraversal(root)) # [1,2,4,5,3]
print(inorderTraversal(root)) # [4,5,2,3,1]
print(postorderTraversal(root)) # [4,5,2,3,1]