145. Binary Tree Postorder Traversal
Problem
Given the root of a binary tree, return the postorder traversal of its nodes’ values.
https://leetcode.com/problems/binary-tree-postorder-traversal/
Example 1:
Input:
root = [1,null,2,3]
Output:[3,2,1]
Explanation:case1
Example 2:
Input:
root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output:[4,6,7,5,2,9,8,3,1]
Explanation:case2
Example 3:
Input:
root = []
Output:[]
Example 4:
Input:
root = [1]
Output:[1]
Constraints:
- The number of the nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Follow up: Recursive solution is trivial, could you do it iteratively?
Test Cases
# 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]:solution_test.py下载完整源码
import pytest
import os
import sys
sys.path.append(os.path.dirname(os.path.dirname(__file__)))
from _utils.binary_tree import build_tree
from solution import Solution
null = None
@pytest.mark.parametrize('root, expected', [
([1,null,2,3], [3,2,1]),
([1,2,3,4,5,null,8,null,null,6,7,9], [4,6,7,5,2,9,8,3,1]),
([], []),
([1], [1]),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, root, expected):
assert sol.postorderTraversal(build_tree(root)) == expected
Thoughts
在 124. Binary Tree Maximum Path Sum 或 337. House Robber III 中都用到了基于栈的非递归后序遍历二叉树。
Code
solution.py下载完整源码
from typing import Optional
# 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]:
res = []
stack = []
prev = None
while root or stack:
if root:
stack.append(root)
root = root.left
elif stack[-1].right != prev:
root = stack[-1].right
prev = None
else:
prev = stack.pop()
res.append(prev.val)
return res
评论需要 JavaScript。