`

Leetcode - Binary Tree Postorder

 
阅读更多
[分析]
迭代实现后序遍历比迭代实现先序和中序都要稍微复杂,对其一直有恐惧心理,总觉得自己不看答案做不出来……这次竟然做出来了,很开心,练习还是有效果的~
思路1:遍历到curr节点,不管三七二十一,入栈,继续访问左节点,因为后序遍历中root最后访问。问题是栈中的节点何时出栈?答案是其左右节点均被访问之后。怎么判断其左右节点均被访问过了呢?或者换个问题,怎么判断右节点没有被访问过(一路向左,左节点必然先被访问了)?答案是如果栈顶元素有右节点且右节点没有出现在结果列表的最后。
思路2:先序遍历是root->left->right,后序遍历是left->right->root,因此修改下先序遍历实现,让其访问顺序变为root->right->left,则逆序所得结果即为后序遍历结果。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    // Method 2: modification of preorder from root->left->right to root->right->left
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> postorder = new ArrayList<Integer>();
        if (root == null) return postorder;
        LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                postorder.add(curr.val);
                if (curr.left != null)
                    stack.push(curr.left);
                curr = curr.right;
            } else {
                curr = stack.pop();
            }
        }
        Collections.reverse(postorder);
        return postorder;
    }
    // Method 1
    public List<Integer> postorderTraversal1(TreeNode root) {
        List<Integer> ret = new ArrayList<Integer>();
        if (root == null) return ret;
        LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            } else {
                TreeNode top = stack.peek();
                if (top.right != null && (ret.size() == 0 || ret.get(ret.size() - 1) != top.right.val))
                    curr = top.right; // right child has not been visited
                else // no right child or has been visited
                    ret.add(stack.pop().val);
            }
        }
        return ret;
    }
}
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics