LeetCode[145] Binary Tree Postorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values.

For example:
Given binary tree {1,null,2,3},

1
\
2
/
3

return [3,2,1].

分析:

两种种方法:

  1. 递归法

    递归是最简单的。

  2. 迭代法

代码:

递归法:

public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<Integer>();
if (root != null) {
result.addAll(inorderTraversal(root.left));
result.addAll(inorderTraversal(root.right));
result.add(root.val);
}
return result;
}
}

迭代法:

public class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> result = new LinkedList<Integer>();
if (root == null) return result;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode n = root;
stack.push(n);
while (!stack.empty()) {
n = stack.pop();
result.addFirst(n.val);
if (n.left != null) stack.push(n.left);
if (n.right != null) stack.push(n.right);
}
return result;
}
}

欢迎关注公众号: FullStackPlan 获取更多干货

Copyright © 2016 - 2017 LBD All Rights Reserved.

访客数 : | 访问量 :