Python_算法_二叉树

发表于 本文字数： 6.7k 阅读时长 ≈ 6 分钟

递归法、迭代法、广度优先法

二叉树 - 前中后序遍历 - 递归法

使用递归法，发现其实只是根节点放在什么地方而已。
前序：根-左-右
中序：左-中-右
后序：左-右-中

  1. 前序遍历 - 递归法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    # 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]:
            def get_forward_nodes(node):
                p_list = []
                p_list += [node.val]
                if node.left:
                    p_list += get_forward_nodes(node.left)
                if node.right:
                    p_list += get_forward_nodes(node.right)
                return p_list
            return get_forward_nodes(root) if root else []

  2. 中序遍历 - 递归法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    # 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
            def get_forward_nodes(node):
                p_list = []
                if node.left:
                    p_list += get_forward_nodes(node.left)
                p_list += [node.val]
                if node.right:
                    p_list += get_forward_nodes(node.right)
                return p_list
            return get_forward_nodes(root) if root else []

  3. 后续遍历 - 递归法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    # 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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
            def get_forward_nodes(node):
                p_list = []
                if node.left:
                    p_list += get_forward_nodes(node.left)
                if node.right:
                    p_list += get_forward_nodes(node.right)
                p_list += [node.val]
                return p_list
            return get_forward_nodes(root) if root else []```

  4. 层序遍历

    迭代法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    # 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
            def get_level_nodes(nodes):
                current_nodes = []
                next_nodes = []
                for node in nodes:
                    current_nodes.append(node.val)
                    if node.left:
                        next_nodes.append(node.left)
                    if node.right:
                        next_nodes.append(node.right)
                return current_nodes, next_nodes
            
            result_nodes = []
            if root:
                next_nodes = [root]
                while next_nodes:
                    current_nodes, next_nodes = get_level_nodes(next_nodes)
                    result_nodes.append(current_nodes)
            else:
                return []
            return result_nodes

  5. BFS算法（广度优先搜索）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    # 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
            dq = deque([]) # 栈
            if not root:
                return []
            dq.append(root)
            result_list = []
            while dq:
                current_level_nodes = []
                dq_size = len(dq)
                while dq_size:
                    popleft_node = dq.popleft()
                    dq_size -= 1
                    current_level_nodes.append(popleft_node.val)
                    if popleft_node.left:
                        dq.append(popleft_node.left)
                    if popleft_node.right:
                        dq.append(popleft_node.right)
                result_list.append(current_level_nodes)
            return result_list

    另：BFS 广度优先搜索一般用来查询 层序遍历，引申出二叉树最短路径的问题

二叉树 - 最大深度

  1. BFS

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    # 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 maxDepth(self, root: Optional[TreeNode]) -> int:
            
            if not root:
                return 0
            dq = deque([])
            dq.append(root)
            max_len = 0
            while dq:
                max_len += 1
                dq_size = len(dq)
                while dq_size:
                    dq_size -= 1
                    node = dq.popleft()
                    if node.left:
                        dq.append(node.left)
                    if node.right:
                        dq.append(node.right)
            return max_len

  2. 递归法

    递归法真的是太简洁了

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    # 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 maxDepth(self, root: Optional[TreeNode]) -> int:
            def get_depth(node):
                return 0 if not node else max(get_depth(node.left)+1, get_depth(node.right)+1)
            return get_depth(root)

对称二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def get_left_node_tree(node):
            current_node_vals = []
            if not node:
                return []
            current_node_vals.append(node.val)
            if node.left:
                current_node_vals += get_left_node_tree(node.left)
            else:
                current_node_vals.append(None)
            if node.right:
                current_node_vals += get_left_node_tree(node.right)
            else:
                current_node_vals.append(None)
            return current_node_vals

        def get_right_node_tree(node):
            if not node:
                return []
            current_node_vals = []
            current_node_vals.append(node.val)
            if node.right:
                current_node_vals += get_right_node_tree(node.right)
            else:
                current_node_vals.append(None)
            if node.left:
                current_node_vals += get_right_node_tree(node.left)
            else:
                current_node_vals.append(None)
            return current_node_vals
        if get_left_node_tree(root.left) != get_right_node_tree(root.right):
            return False
        else:
            return True