代码随想录算法训练营第十四天|二叉树前序/中序/后续遍历

二叉树前序/中序/后续遍历

前序遍历

#  !/usr/bin/env  python
#  -*- coding:utf-8 -*-
# @Time   :  2022.11
# @Author :  hello algorithm!
# @Note   :  https://leetcode.cn/problems/binary-tree-preorder-traversal/
from typing import Optional, List


# 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 preorderTraversaldfs(self, root: Optional[TreeNode]) -> List[int]:
        """
        递归三部曲
        1. 定义递归函数(参数+返回值)
        2. 确定递归终止条件
        3. 确定递归函数单层逻辑
        """
        result = []

        # 1. 定义递归函数
        def traversal(cur_node: Optional[TreeNode], result: List[int]) -> None:
            # 2. 确定递归终止条件：遍历到空节点后，递归结束
            if cur_node is None:
                return
            # 3. 确定递归函数单层逻辑
            # 遍历中节点
            result.append(cur_node.val)
            # 遍历左节点, 右节点
            traversal(cur_node.left, result)
            # 遍历右节点
            traversal(cur_node.right, result)

        traversal(root, result)
        return result

    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        """
        1. 使用栈，当栈非空时，进入循环
        2. 从栈pop出节点node，将node的val放到result数组中，当node的右孩子非空时，将右孩子放到栈中，同理队左孩子进行同样操作
        3. 当栈为空时，返回最终结果
        :param root: 根节点
        :return: None
        """
        result = []

        def travarsal(root: Optional[TreeNode]) -> None:
            stack = []
            if root:
                stack.append(root)

            while stack:
                node = stack.pop()
                result.append(node.val)
                # 注意，先放右节点，再放左节点+还有判空条件哦！
                if node.right:
                    stack.append(node.right)
                if node.left:
                    stack.append(node.left)

        travarsal(root)
        return result


if __name__ == '__main__':
    pass

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

中序遍历

#  !/usr/bin/env  python
#  -*- coding:utf-8 -*-
# @Time   :  2022.11
# @Author :  hello algorithm!
# @Note   :  https://leetcode.cn/problems/binary-tree-postorder-traversal/
from typing import Optional, List


# 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 inorderTraversalself(self, root: Optional[TreeNode]) -> List[int]:
        """
        递归三部曲
        1. 定义递归函数(参数+返回值)
        2. 确定递归终止条件
        3. 确定递归函数单层逻辑
        """
        result = []

        # 1. 定义递归函数
        def traversal(cur_node: Optional[TreeNode], result: List[int]) -> None:
            # 2. 确定递归终止条件：遍历到空节点后，递归结束
            if cur_node is None:
                return
            # 3. 确定递归函数单层逻辑
            # 遍历左节点
            traversal(cur_node.left, result)
            # 遍历中节点
            result.append(cur_node.val)
            # 遍历右节点
            traversal(cur_node.right, result)

        traversal(root, result)
        return result

    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        """
        迭代法
        遍历节点和处理节点不一致，需要定义一个辅助指针cur_node，不撞南墙不回头
        1. 当栈stack或者辅助指针cur_node不为空时，进入循环
        2. cur_node不为空时cur_node入栈cur_node = cur_node.left/right
        3. 当cur_node为空时，stack弹出node，将node.val加入返回列表result中，将cur_node = node.right非空时入栈
        """
        result = []

        # 1. 定义递归函数
        def traversal(root: Optional[TreeNode]) -> None:
            stack = []
            cur_node = root
            if cur_node:
                stack.append(cur_node)

            while stack or cur_node:
                if cur_node:
                    cur_node = cur_node.left
                    if cur_node:
                        stack.append(cur_node)
                else:
                    cur_node = stack.pop()
                    result.append(cur_node.val)
                    cur_node = cur_node.right
                    if cur_node:
                        stack.append(cur_node)

        traversal(root)
        return result


if __name__ == '__main__':
    pass
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

后续遍历

#  !/usr/bin/env  python
#  -*- coding:utf-8 -*-
# @Time   :  2022.11
# @Author :  hello algorithm!
# @Note   :  https://leetcode.cn/problems/binary-tree-postorder-traversal/
from typing import Optional, List


# 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]:
        result = []

        # 1. 定义递归函数
        def traversal(cur_node: Optional[TreeNode], result: List[int]) -> None:
            # 2. 确定递归终止条件：遍历到空节点后，递归结束
            if cur_node is None:
                return
            # 3. 确定递归函数单层逻辑
            # 遍历左节点
            traversal(cur_node.left, result)
            # 遍历右节点
            traversal(cur_node.right, result)
            # 遍历中节点
            result.append(cur_node.val)

        traversal(root, result)
        return result


if __name__ == '__main__':
    pass

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