Leetcode 145.后序遍历

Posted on |

145. 二叉树的后序遍历

题目

给定一个二叉树，返回它的 后序 遍历。

1
2
3
4
5
6
7
8
9
10
示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3

输出: [3,2,1]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

方法

方法1：递归

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, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        ans=[]
        def recursive(node):
            if not node:
                return

            recursive(node.left)
            recursive(node.right)
            ans.append(node.val)
        recursive(root)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        result = self.postorderTraversal(root.left)
        result += self.postorderTraversal(root.right)
        return result + [root.val]

方法2：迭代

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

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

# class Solution(object):
#     def postorderTraversal(self, root):
#         """
#         :type root: TreeNode
#         :rtype: List[List[int]]
#         """
#         res = []
#         if not root:
#             return res
#         res.extend(self.postorderTraversal(root.left))
#         res.extend(self.postorderTraversal(root.right))
#         res.append(root.val)
#         return res

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        res = []
        if not root:
            return res
        stack = [root]
        while stack:
            node = stack.pop()
            res.append(node.val)
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        return list(reversed(res))
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(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        ans,stack=[],[]
        while root or stack:
            while root:
                stack.append(root)
                root=root.left if root.left else root.right

            root=stack.pop()
            ans.append(root.val)
            if stack and stack[-1].left==root:
                root=stack[-1].right
            else:
                root=None
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """

        res, stack = [], [root]
        while stack:
            node = stack.pop()
            if node:
                res.append(node.val)
                stack.append(node.left)     # 整体上和先序遍历差不多，差别就在于左分支和右分支入栈顺序，以及返回
                stack.append(node.right)
        return res[::-1]