首页 > itarticle > [leetcode] problem 145 – binary tree postorder traversal

[leetcode] problem 145 – binary tree postorder traversal

admin 11月 13, 2020 0

Given a binary tree, return the postorder traversal of its nodes’ values.

Example

Input: [1,null,2,3]

Output: [3,2,1]

Follow up

Recursive solution is trivial, could you do it iteratively?

Code

public class  {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new LinkedList<>();

    if (root == null)
        return result;

    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(0, node.val);

        if (node.left != null)
            stack.push(node.left);

        if (node.right != null)
            stack.push(node.right);
    }

    return result;
}