[LeetCode/LintCode] Binary Tree Postorder Traversa

Amio 發(fā)布于2019-08-14 15:48 / 3288人閱讀

摘要：不用遞歸嗎沒問題，我們用做，速度驚人。對于左子樹，放入鏈表對于右子樹，直接移動。這樣每次用將放入結(jié)果數(shù)組的首位，再將放入首位，每次再將的左子樹放入鏈表，當(dāng)右子樹遍歷完后，再從鏈表中以的順序取出從上到下的左子樹結(jié)點，以相同方法放入首位。

Problem

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

For example:
Given binary tree {1,#,2,3},

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

不用遞歸嗎？沒問題，我們用LinkedList做，速度驚人。對于左子樹，放入鏈表；對于右子樹，直接移動node：node = node.right。這樣每次用addFirst()將node放入結(jié)果數(shù)組的首位，再將root.right放入首位，每次再將root.right的左子樹放入鏈表，當(dāng)右子樹遍歷完后，再從鏈表中以FIFO的順序取出從上到下的左子樹結(jié)點，以相同方法放入首位。

Solution Using LinkedList

public class Solution {
    public List postorderTraversal(TreeNode node) {
        LinkedList result = new LinkedList();
        Stack leftChildren = new Stack();
        while(node != null) {
            result.addFirst(node.val);
            if (node.left != null) leftChildren.push(node.left);
            node = node.right;
            if (node == null && !leftChildren.isEmpty()) node = leftChildren.pop();
        }
        return result;
    }
}

Using Recursion

public class Solution {
    public List postorderTraversal(TreeNode root) {
        ArrayList res = new ArrayList();
        if (root == null) return res;
        helper(root, res);
        return res;
    }
    public void helper(TreeNode root, ArrayList res) {
        if (root.left != null) helper(root.left, res);
        if (root.right != null) helper(root.right, res);
        res.add(root.val);
    }
}