【学习记录】二叉树递归前中后序遍历

最近终于系统学一遍二叉树遍历,回顾笔记

递归定义

递归三要素

1. 确定递归函数的参数和返回值

2. 确定终止条件

3. 确定单层递归的逻辑

代码

前序遍历

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
    
        def loop_traversals(root):
            if root == None:
                return
            res.append(root.val)
            loop_traversals(root.left)
            loop_traversals(root.right)

        loop_traversals(root)
        return res 


        
    def preorderTraversal_leetcode(self,root):
        if not root:return []
        ans,stack = [],[root]
        while stack:
            curr = stack.pop()
            ans.append(curr.val)

            if curr.right:
                stack.append(curr.right)
            if curr.left:
                stack.append(curr.left)

        return ans
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

中序遍历

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = [] 

        def loop_traversals(root):
            if root == None:
                return 

            loop_traversals(root.left)
            res.append(root.val)
            loop_traversals(root.right)
        loop_traversals(root)
        return res 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

后序遍历

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res =[]
        def loop(root):
            if root == None:return 
            loop(root.left)
            loop(root.right)
            res.append(root.val)
        loop(root)
        return res 
        ```

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22