首页 / JAVA / Binary Tree Postorder Traversal leetcode java

Binary Tree Postorder Traversal leetcode java

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Binary Tree Postorder Traversal leetcode java，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2005字，纯文字阅读大概需要3分钟。

内容图文

题目：

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

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

   1
         2
    /
   3

return [3,2,1].

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

 

题解：

递归方法代码：

 1     public void helper(TreeNode root, ArrayList<Integer> re){
 2         if(root==null)
 3             return;
 4         
 5         helper(root.left,re);
 6         helper(root.right,re);
 7         re.add(root.val);
 8     }
 9     public ArrayList<Integer> postorderTraversal(TreeNode root) {
10         ArrayList<Integer> re = new ArrayList<Integer>();
11         if(root==null)
12             return re;
13         helper(root,re);
14         return re;
15     }

 非递归方法代码：

 引用自Code ganker：http://blog.csdn.net/linhuanmars/article/details/22009351

“接下来是迭代的做法，本质就是用一个栈来模拟递归的过程，但是相比于Binary Tree Inorder Traversal和Binary Tree Preorder Traversal，后序遍历的情况就复杂多了。我们需要维护当前遍历的cur指针和前一个遍历的pre指针来追溯当前的情况（注意这里是遍历的指针，并不是真正按后序访问顺序的结点）。具体分为几种情况：
（1）如果pre的左孩子或者右孩子是cur，那么说明遍历在往下走，按访问顺序继续，即如果有左孩子，则是左孩子进栈，否则如果有右孩子，则是右孩子进栈，如果左右孩子都没有，则说明该结点是叶子，可以直接访问并把结点出栈了。
（2）如果反过来，cur的左孩子是pre，则说明已经在回溯往上走了，但是我们知道后序遍历要左右孩子走完才可以访问自己，所以这里如果有右孩子还需要把右孩子进栈，否则说明已经到自己了，可以访问并且出栈了。
（3）如果cur的右孩子是pre，那么说明左右孩子都访问结束了，可以轮到自己了，访问并且出栈即可。
算法时间复杂度也是O(n)，空间复杂度是栈的大小O(logn)。实现的代码如下：”

 1 public ArrayList<Integer> postorderTraversal(TreeNode root) {
 2     ArrayList<Integer> res = new ArrayList<Integer>();
 3     if(root == null)
 4         return res;
 5     LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
 6     stack.push(root);
 7     TreeNode pre = null;
 8     while(!stack.isEmpty()){
 9         TreeNode cur = stack.peek();
10         if(pre==null || pre.left==cur || pre.right==cur){
11             if(cur.left!=null)
12                 stack.push(cur.left);
13             else if(cur.right!=null)
14                 stack.push(cur.right);
15             else
16                 res.add(cur.val);
17                 stack.pop();
18         }
19         else if(cur.left==pre && cur.right!=null){
20             stack.push(cur.right);
21         }else{
22             res.add(cur.val);
23             stack.pop();
24         }
25         pre = cur;
26     }
27     return res;
28 }

原文：http://www.cnblogs.com/springfor/p/3877260.html

内容总结

以上是互联网集市为您收集整理的Binary Tree Postorder Traversal leetcode java全部内容，希望文章能够帮你解决Binary Tree Postorder Traversal leetcode java所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1250289.html

来源：【匿名】