1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
|
递归实现: public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>(); postOrder2(root, res); retu-rn res; }
public void postOrder2(TreeNode root, List<Integer> res) { if (root.left != null) { postOrder2(root.left, res); } if (root.right != null) { postOrder2(root.right, res); } res.add(root.val); }
非递归实现: public List<Integer> postorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); Stack<Integer> res = new Stack<>(); Stack<TreeNode> stack = new Stack<>(); if (root == null) { return res; } TreeNode node = root; while (node != null || !stack.empty()) { if (node != null) { res.push(node.val); stack.push(node); node = node.right; } else { node = stack.pop(); node = node.left; } } while(!res.empty()){ result.add(res.pop()); } return result; }
|
近期评论