首页 > 代码库 > 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?
Solution:
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */10 public class Solution {11 public List<Integer> postorderTraversal(TreeNode root) {12 List<Integer> res = new ArrayList<Integer>();13 if (root==null) return res;14 15 Stack<TreeNode> nStack = new Stack<TreeNode>();16 Stack<Integer> record = new Stack<Integer>();17 nStack.push(root);18 record.push(0);19 20 while (nStack.size()!=0){21 TreeNode cur = nStack.peek();22 if (cur.left==null && cur.right==null){23 res.add(cur.val);24 nStack.pop();25 record.pop();26 continue;27 }28 29 int val = record.peek();30 if (val==0){31 record.pop();32 record.push(val+1);33 if (cur.left!=null){34 nStack.push(cur.left);35 record.push(0);36 }37 continue;38 }39 40 if (val==1){41 record.pop();42 record.push(val+1);43 if (cur.right!=null){44 nStack.push(cur.right);45 record.push(0);46 }47 continue;48 }49 50 if (val==2){51 res.add(cur.val);52 nStack.pop();53 record.pop();54 continue;55 }56 }57 58 return res; 59 60 }61 }
Leetcode-Binary Tree Postorder Traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。