首页 > 代码库 > LeetCode解题报告:Binary Tree Postorder Traversal
LeetCode解题报告: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?
注意:下面是迭代的解法。理解有点困难,和大家讨论一下。
1 import java.util.ArrayList; 2 import java.util.List; 3 import java.util.Stack; 4 5 /** 6 * Definition for binary tree public class TreeNode { int val; TreeNode left; 7 * TreeNode right; TreeNode(int x) { val = x; } } 8 */ 9 public class TreeNodeNoneReverse {10 List<Integer> postOrder = new ArrayList<Integer>();11 12 public List<Integer> postorderTraversal(TreeNode root) {13 // 非递归实现后序遍历14 TreeNode tempTree = root;15 Stack<TreeNode> stack = new Stack<TreeNode>();16 while (root != null) {17 // 左子树入栈18 for (; root.left != null; root = root.left) {19 System.out.println("左子树入栈:" + root.val);20 stack.push(root);21 }22 // 当前节点无右子或右子已经输出23 while (root != null24 && (root.right == null || root.right == tempTree)) {25 System.out.println("add list:" + root.val);26 postOrder.add(root.val);27 tempTree = root;// 记录上一个已输出节点28 System.out.println("上一个已输出的节点:"+tempTree.val);29 if (stack.empty()) {30 System.out.println("stack is empty.");31 return postOrder;32 }33 root = stack.pop();34 System.out.println("右子树出栈:" + root.val);35 }36 // 处理右子37 System.out.println("处理右子入栈:" + root.val);38 stack.push(root);39 root = root.right;40 }41 System.out.println("可能运行到这儿么?");42 return postOrder;43 }44 45 public static void main(String[] args) {46 TreeNode t1 = new TreeNode(1);47 TreeNode t2 = new TreeNode(2);48 TreeNode t3 = new TreeNode(3);49 TreeNode t4 = new TreeNode(4);50 TreeNode t5 = new TreeNode(5);51 TreeNode t6 = new TreeNode(6);52 t3.setLeft(t2);53 t3.setRight(t1);54 t2.setLeft(t4);55 t2.setRight(t5);56 t1.setRight(t6);57 System.out.println(new TreeNodeNoneReverse().postorderTraversal(t3));58 }59 }60
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。