首页 > 代码库 > LeetCode: Binary Tree Postorder Traversal 解题报告
LeetCode: Binary Tree Postorder Traversal 解题报告
Binary Tree Postorder Traversal
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?
Show Tags
Have you met this question in a real interview? Yes No
Discuss
SOLUTION 1:
递归解法
1 public List<Integer> postorderTraversal1(TreeNode root) { 2 List<Integer> ret = new ArrayList<Integer>(); 3 dfs(root, ret); 4 return ret; 5 } 6 7 // Solution 1: rec 8 public void dfs(TreeNode root, List<Integer> ret) { 9 if (root == null) {10 return;11 }12 13 dfs(root.left, ret);14 dfs(root.right, ret);15 ret.add(root.val);16 }
SOLUTION 2:
/**
* 后序遍历迭代解法
* http://www.youtube.com/watch?v=hv-mJUs5mvU
* http://blog.csdn.net/tang_jin2015/article/details/8545457
* 从左到右的后序 与从右到左的前序的逆序是一样的，所以就简单喽！ 哈哈
* 用另外一个栈进行翻转即可喽
*/
1 // Solution 2: iterator 2 public List<Integer> postorderTraversal(TreeNode root) { 3 List<Integer> ret = new ArrayList<Integer>(); 4 if (root == null) { 5 return ret; 6 } 7 8 Stack<TreeNode> s = new Stack<TreeNode>(); 9 Stack<Integer> out = new Stack<Integer>();10 11 s.push(root);12 13 while (!s.isEmpty()) {14 TreeNode cur = s.pop();15 out.push(cur.val);16 17 if (cur.left != null) {18 s.push(cur.left);19 }20 21 if (cur.right != null) {22 s.push(cur.right);23 }24 }25 26 while (!out.isEmpty()) {27 ret.add(out.pop());28 }29 30 return ret;31 }
GITHUB:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/tree/PostorderTraversal.java
LeetCode: Binary Tree Postorder Traversal 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。