数据结构 – 二叉树刷题

基本性质

每个结点的度最多为 2。
度为 0 的结点比度为 2 的结点多一个。
证明：设度为 0 的结点为 n0，度为 1 的结点为 n1，度为 2 的结点为 n2。那么总结点数为 n0 + n1 + n2，而总边数为 0 · n0 + 1 · n1 + 2 · n2。而我们知道总边数等于总结点数减去 1，那么有 n0 + n1 + n2 − 1 = 0 · n0 + 1 · n1 + 2 · n2，即 n0 − 1 = n2。

遍历

根据根结点被访问的时机，分为前序遍历（根、左子树、右子树）、中序遍历（左子树、根、右子树）和后序遍历（左子树、右子树、根）。

特殊的二叉树

完全二叉树 (complete binary tree)
满二叉树 (full binary tree) – 指所有结点的度都是 0 或 2 的二叉树
完美二叉树 (perfect binary tree)
注：几种二叉树的定义在不同的资料说明中可能存在一定差异，因此在实际场合中提到时请务必进行确认。

树结构的理解

结点表示集合 (set)，边表示关系 (relationship)。

学习二叉树的作用

二叉树是理解高级数据结构的基础。

完全二叉树 – 堆、优先队列
多叉树/森林 – 字典树、AC 自动机、并查集
二叉排序树 (BST, Binary Search Tree) – AVL 树、2-3 树、红黑树、B-树、
B+ 树二叉树是练习递归技巧的最佳选择。学习二叉树后，可以使用左孩子右兄弟法来节省空间。

二叉树的基本操作

LeetCode 144. 二叉树的前序遍历

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        if not root:
            return []
        def get_help(root):
            if not root:
                return 
            # 根左右 
            result.append(root.val)
            get_help(root.left)
            get_help(root.right)
        get_help(root)
        return result

LeetCode 589. N 叉树的前序遍历

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        if not root:
            return 
        result = []
        queue = collections.deque()
        queue.append(root)
        while queue:
            node = queue.pop()
            result.append(node.val)
            for child in node.children[::-1]:
                queue.append(child)
        return result

LeetCode 226. 翻转二叉树

思路: 交换左右子树，再递归翻转左右子树。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return 
        tmp = self.invertTree(root.left)
        root.left = self.invertTree(root.right)
        root.right = tmp
        return root

LeetCode 剑指 Offer 32 – II. 从上到下打印二叉树 II

使用将行号作为参数的递归即可。也可以使用队列 BFS 来进行层序遍历

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        result  = []
        queue = collections.deque()
        queue.append(root)
        while queue:
            tmp = []
            for _ in range(len(queue)):
                node = queue.popleft()
                tmp.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(tmp)
        return result

LeetCode 107. 二叉树的层序遍历 II

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        result = []
        queue = collections.deque()
        queue.append(root)
        while queue:
            tmp = []
            for _ in range(len(queue)):
                node  = queue.popleft()
                tmp.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(tmp)
        result = result[::-1]
        return result

LeetCode 103. 二叉树的锯齿形层序遍历

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        result = []
        queue = collections.deque()
        queue.append(root)
        flag = True
        while queue:
            tmp = []
            for _ in range(len(queue)):
                node = queue.popleft()
                tmp.append(node.val)
                if node.left:
                    queue.append(node.left)    
                if node.right:
                    queue.append(node.right)
            if flag:
                result.append(tmp)
            else:
                result.append(tmp[::-1])
            flag = not flag
            # result.append(tmp)
        return result