首页 > 代码库 > 后序遍历
后序遍历
一些大神的总结
http://blog.sina.com.cn/s/blog_eb52001d0102v1si.html
递归的两种,写在一个方法里或者两个
Recursive
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param root: The root of binary tree. * @return: Postorder in ArrayList which contains node values. */ public ArrayList<Integer> postorderTraversal(TreeNode root) { // write your code here ArrayList<Integer> result = new ArrayList<Integer>(); traverse(root, result); return result; } private void traverse(TreeNode root, ArrayList<Integer> result) { if (root == null) { return; } traverse(root.left, result); traverse(root.right, result); result.add(root.val); } }
public ArrayList<Integer> postorderTraversal(TreeNode root) { ArrayList<Integer> result = new ArrayList<Integer>(); if (root == null) { return result; } result.addAll(postorderTraversal(root.left)); result.addAll(postorderTraversal(root.right)); result.add(root.val); return result; }
分治
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param root: The root of binary tree. * @return: Postorder in ArrayList which contains node values. */ public ArrayList<Integer> postorderTraversal(TreeNode root) { // write your code here ArrayList<Integer> result = new ArrayList<Integer>(); if (root == null) { return result;//不能只写return,注意要求返回类型 } //divide ArrayList<Integer> left = postorderTraversal(root.left); ArrayList<Integer> right = postorderTraversal(root.right); //conquer result.addAll(left); result.addAll(right); result.add(root.val);//又忘了!!!!root.val not root!! return result; } }
非递归
//Iterative public ArrayList<Integer> postorderTraversal(TreeNode root) { ArrayList<Integer> result = new ArrayList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode prev = null; // previously traversed node TreeNode curr = root; if (root == null) { return result; } stack.push(root); while (!stack.empty()) { curr = stack.peek(); if (prev == null || prev.left == curr || prev.right == curr) { // traverse down the tree if (curr.left != null) { stack.push(curr.left); } else if (curr.right != null) { stack.push(curr.right); } } else if (curr.left == prev) { // traverse up the tree from the left if (curr.right != null) { stack.push(curr.right); } } else { // traverse up the tree from the right result.add(curr.val); stack.pop(); } prev = curr; } return result; }
后序遍历
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。