首页 > 其他 > 详细

Binary Tree Postorder Traversal

时间:2015-03-17 21:24:09      阅读:279      评论:0      收藏:0      [点我收藏+]

Binary Tree Postorder Traversal 

问题:

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

思路:

  栈方法

我的代码:

技术分享
public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> rst = new ArrayList<Integer>();
        if(root == null) return rst;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while(!stack.isEmpty())
        {
            TreeNode node = stack.pop();
            rst.add(0,node.val);
            if(node.left != null)
                stack.push(node.left);
            if(node.right != null)
                stack.push(node.right);
        }
        return rst;
    }
}
View Code

学习之处:

  • 递归的前序,中序,后序是很好写的,关键在于非递归应该怎么写,无论怎么写都需要使用栈,因为递归==栈
  • 前序 root left right 所以压栈的方式是,弹出根节点,压入right 然后压入left 这样便能实现输出 root left right
  • 中序 一直压栈直到压完root的left 形成的结果是 left 弹栈,left 同时判断弹出的是否有right,若有,继续压left 栈里面的效果是 left
  • 后序遍历 弹出root,压入left,压入right 所以栈里面的效果是left right,经典之处在于每一次弹出节点都是插入到节点的前面 弹出root后的下一个节点弄得,插入到root的前面,就如同当前问题我的代码里描述的那样。

Binary Tree Postorder Traversal

原文:http://www.cnblogs.com/sunshisonghit/p/4345358.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!