# 总结了一些二叉树操作的干货……

01 二叉树遍历

• 前序：1-2-4-5-3-6
• 中序：4-2-5-1-3-6
• 后序：4-5-2-6-3-1
• 层级遍历：1-2-3-4-5-6

1class Solution:
2    def preorderTraversal(self, root: TreeNode) -> List[int]:
3        self.res = []
4        self.dfs(root)
5        return self.res
6
7    def dfs(self, node):
8        if not node: return
9        self.res.append(node.val)
10        self.dfs(node.left)
11        self.dfs(node.right)

1class Solution:
2    def preorderTraversal(self, root: TreeNode) -> List[int]:
3        return [root.val]+self.preorderTraversal(root.left)+self.preorderTraversal(root.right) if root else []

1class Solution:
2    def preorderTraversal(self, root: TreeNode) -> List[int]:
3        stack = [root]
4        values = []
5        while stack:
6            s = stack.pop()
7            if s:
8                values.append(s.val)
9                stack.append(s.right)
10                stack.append(s.left)
11        return values

1class Solution:
2    def inorderTraversal(self, root: TreeNode) -> List[int]:
3        res = []
4        stack = []
5        p = root
6        while p or stack:
7            while p:
8                stack.append(p)
9                p = p.left
10            p = stack.pop()
11            res.append(p.val)
12            p = p.right
13        return res

1class Solution:
2    def postorderTraversal(self, root):
3        if root is None:
4            return []
5        result = []
6        stack = [root]
7        while stack:
8            p = stack.pop()
9            result.append(p.val)
10            if p.left:
11                stack.append(p.left)
12            if p.right:
13                stack.append(p.right)
14        return result[::-1]

1class Solution:
2    def preorderTraversal(self, root: TreeNode) -> List[int]:
3        nodes = [(root, False)]
4        res = []
5        while nodes:
6            node, seen = nodes.pop()
7            if not node:
8                continue
9            elif seen:
10                res.append(node.val)
11            else:
12                nodes.append((node.right, False))
13                nodes.append((node.left, False))
14                nodes.append((node, True))
15        return res

1class Solution:
2    def levelOrder(self, root: TreeNode) -> List[List[int]]:
3        nodes, res = [root], []
4        while nodes:
5            res.append([node.val for node in nodes if node])
6            nodes = [n for node in nodes for n in [node.left, node.right]]
7        return res

02 对称二叉树

• 左右节点取值相等
• 左节点的左子树与右节点的右子树镜像
• 左节点的右子树与右节点的左子树镜像

1class Solution:
2    def isSymmetric(self, root: TreeNode) -> bool:
3        def helper(l_tree, r_tree):
4            if l_tree and r_tree:
5                return l_tree.val == r_tree.val and helper(l_tree.left, r_tree.right) and helper(l_tree.right, r_tree.left)
6            if not l_tree and not r_tree:
7                return True
8            else:
9                return False
10        if not root: return True
11        return helper(root.left ,root.right)

1class Solution:
2    def isSymmetric(self, root: TreeNode) -> bool:
3        def check(l, r):
4            if l and r and l.val == r.val:
5                return check(l.left, r.right) and check(l.right, r.left)
6            return l == r
7        return check(root, root)

1class Solution:
2    def isSymmetric(self, root: TreeNode) -> bool:
3        nodes,vals = [root], []
4        while nodes:
5            vals = [node.val if node else '' for node in nodes]
6            if vals != vals[::-1]:
7                return False
8            nodes = [n for node in nodes if node for n in [node.left, node.right]]
9        return True

1class Solution:
2    def isSymmetric(self, root: TreeNode) -> bool:
3        def check(p,q):
4            if not p and not q:
5                return True
6            if not p or not q or p.val!=q.val:
7                return False
8            return True
9
10        if not root:
11            return True
12        queue=deque()
13        queue.append((root.left,root.right))
14        while queue:
15            p,q=queue.popleft()
16            if not check(p,q):
17                return False
18            if p:
19                queue.append((p.left,q.right))
20                queue.append((p.right,q.left))
21        return True

03 恢复二叉树

1class Solution:
2    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
3        def helper(left=0, right=len(inorder)-1):
4            if right<left:
5                return None
6            rootVal = postorder.pop()
7            index = inorder.index(rootVal)
8            root = TreeNode(rootVal)
9            root.right = helper(index+1, right)
10            root.left = helper(left, index-1)
11            return root
12        return helper()

1class Solution:
2    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
3        maps = {val:index for index, val in enumerate(inorder)}
4        def helper(left=0, right=len(inorder)-1):
5            if right<left:
6                return None
7            rootVal = postorder.pop()
8            index = maps[rootVal]
9            root = TreeNode(rootVal)
10            root.right = helper(index+1, right)
11            root.left = helper(left, index-1)
12            return root
13        return helper()

04 寻找公共祖先寻找公共祖先是指在一颗二叉树中找到给定两个节点的最早公共节点，也存在递归和迭代两种写法。在迭代写法中，首先遍历整个树构建每个节点的前溯节点，进而根据两个节点的前溯节点反向对比，直至找到第一个公共节点。

1class Solution:
2    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
3        if root is None or root==p or root==q:
4            return root
5        left=self.lowestCommonAncestor(root.left,p,q)
6        right=self.lowestCommonAncestor(root.right,p,q)
7        if left==None and right==None:
8            return None
9        elif left!=None and right!=None:
10            return root
11        else:
12            if left==None:
13                return right
14            if right==None:
15                return left

05 序列化与反序列化序列化和反序列是模拟二叉树结构数据的编码和解码的问题，即将一个二叉树结构的数据按一定形式存储为连续序列，反序列化则是根据给定的连续序列形式反推二叉树结构。按照层级遍历的方式进行处理，会比较简单

1class Codec:
2    def serialize(self, root):
3        data = []
4        nodes = [root]
5        while nodes:
6            data.append([node.val if node else 'null' for node in nodes])
7            nodes = [n for node in nodes if node for n in [node.left, node.right]]
8        return data
9
10    def deserialize(self, data):
11        root = TreeNode(data[0][0]) if len(data)>1 else None
12        if not root:
13            return root
14        nodes = [root]
15        for vals in data[1:]:
16            for i in range(len(nodes)):
17                nodes[i].left = TreeNode(vals[i*2]) if vals[i*2] != 'null' else None
18                nodes[i].right = TreeNode(vals[i*2+1]) if vals[i*2+1] != 'null' else None
19            nodes = [n for node in nodes  for n in [node.left, node.right] if n]
20        return root

|
1月前
|

32 0
|
1月前
|

27 1
|
1月前
|

37 0
|
7月前
【霍罗维兹数据结构】二叉树前中后序遍历 | 层序遍历 | 复制二叉树 | 判断两个二叉树全等 | 可满足性问题
【霍罗维兹数据结构】二叉树前中后序遍历 | 层序遍历 | 复制二叉树 | 判断两个二叉树全等 | 可满足性问题
48 0
|
1月前
|
Serverless

23 0
|
1月前
|

49 0
|
C语言

10766 4

166 0

150 0

184 0