首页 > 代码库 > 42: Binary Tree Postorder Traversal
42: Binary Tree Postorder Traversal
/************************************************************************/
/* 42: 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].
* */
/****后序遍历 PostOrder tree 递归复杂度****Time: O(n), Space: O(n).****************************************************************/
/*
* 应用1：
* 计算文件夹所占的磁盘容量时，先要计算根节点下的所有文件夹的大小，然后层层网上
*
* TODO
* */
public List<Integer> postorderTraversal(TreeNode root) { List<Integer> source=new ArrayList<Integer>(); postorderTree(root,source); return source; } private void postorderTree(TreeNode node,List<Integer> nodes) { if(node==null) { return; } System.out.println("pre root-->"+node.val); postorderTree(node.left,nodes); postorderTree(node.right,nodes); nodes.add(node.val); System.out.println("-->"+node.val); } /****后序遍历 PostOrder tree Time: O(n), Space: O(n) 栈迭代方法实现的********************************************************************/ //实现的有点繁琐好像,有没有其他办法呢？ 改进版本见 ：postorderTraversal3 public List<Integer>postorderTraversal2(TreeNode root) { List<Integer> results=new ArrayList<Integer>(); Stack<Map<TreeNode, Boolean> > stack=new Stack<Map<TreeNode, Boolean> >(); TreeNode node=null; node=root; while(node!=null||!stack.isEmpty()) { if(node!=null) { Map<TreeNode, Boolean> temp=new HashMap<TreeNode, Boolean>(); temp.put(node, false); stack.push(temp); node=node.left; } else { Map<TreeNode, Boolean> tempnode= stack.pop(); for (Map.Entry<TreeNode, Boolean> entry :tempnode.entrySet()) { if(entry.getKey().left==null&&entry.getKey().right==null&&entry.getValue()==false) // 弹出叶子节点,按照左节点到右节点的弹出顺序 { results.add(entry.getKey().val); //System.out.println(entry.getKey().val); node=entry.getKey(); node=node.right; } else if(entry.getKey().right!=null&&entry.getValue()==false)// 中间路径上的根节点第一遍时不弹出，设置已访问过 { entry.setValue(true); stack.push(tempnode); node=entry.getKey(); node=node.right; } else // 中间路径上的根节点第二遍时弹出 { results.add(entry.getKey().val); //System.out.println(entry.getKey().val); node=null; } } } } return results; } /****后序遍历 PostOrder tree 简洁版本1 Time: O(n), Space: O(n) 栈迭代方法实现的********************************************************************/ /* * * 算法思路： 对应函数： postorderTraversal3，postorderTraversal4 * * pre-order traversal is root-left-right, and post order is left-right-root. * modify the code for pre-order to make it root-right-left, * and then reverse the output so that we can get left-right-root . Create an empty stack, Push root node to the stack. Do following while stack is not empty. 2.1. pop an item from the stack and print it. 2.2. push the left child of popped item to stack. 2.3. push the right child of popped item to stack. reverse the ouput. * */ public List<Integer>postorderTraversal3(TreeNode root) { List<Integer> results=new ArrayList<Integer>(); Stack<TreeNode> stack=new Stack<TreeNode>(); TreeNode node=null; node=root; while(node!=null||!stack.isEmpty()) { if(node!=null) { //System.out.println("-->"+node.val); results.add(node.val); stack.push(node); node=node.right; } else { node= stack.pop(); node=node.left; } } Collections.reverse(results); return results; } public List<Integer>postorderTraversal4(TreeNode root) { List<Integer> results=new ArrayList<Integer>(); Stack<TreeNode> stack=new Stack<TreeNode>(); stack.push(root); TreeNode node=null; while(!stack.isEmpty()) { node=stack.pop(); results.add(node.val); if(node.left!=null) { stack.push(node.left); } if(node.right!=null) { stack.push(node.right); } } Collections.reverse(results); return results; }
42: Binary Tree Postorder Traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。