[广告]分治/递归 思想总结：http://www.jianshu.com/p/6c1de969830c
- Binary Tree Preorder Traversal
Stack 法一 regular
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null) return list;
// Deque<TreeNode> stack = new LinkedList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while(!stack.isEmpty()) {
TreeNode cur = stack.pop();
list.add(cur.val);
if(cur.right != null) stack.push(cur.right);
if(cur.left != null) stack.push(cur.left);
}
return list;
}
}
Stack 法二. 每个非空都先push，有左走左，没有就pop
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
// Deque<TreeNode> stack = new ArrayDeque<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode cur = root;
while(!stack.isEmpty() || cur != null) {
while(cur != null) {
stack.push(cur);
// process
result.add(cur.val); // Add before going to children
cur = cur.left;
}
cur = stack.pop();
cur = cur.right;
}
return result;
}
}
Stack 法三 (类似二 only right children are stored to the stack)
class Solution {
public List<Integer> preorderTraversal(TreeNode node) {
List<Integer> list = new LinkedList<Integer>();
Deque<TreeNode> rights = new ArrayDeque<TreeNode>();
while(node != null) {
list.add(node.val);
if (node.right != null) {
rights.push(node.right);
}
node = node.left;
if (node == null && !rights.isEmpty()) {
node = rights.pop();
}
}
return list;
}
}
Recursive:
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new LinkedList<Integer>();
preHelper(root, list);
return list;
}
public void preHelper(TreeNode root, List<Integer> list) {
if(root==null) return;
list.add(root.val);
preHelper(root.left, list);
preHelper(root.right, list);
}
}
- Path Sum
Stack 法一 regular
Stack 法二. 每个非空都先push，有左走左，没有就pop
Recursive
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if(root == null) return false;
if(root.left == null && root.right == null && root.val == sum) return true;
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
}
- Path Sum II
Recursive
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> result = new LinkedList<List<Integer>>();
List<Integer> cur_result = new LinkedList<Integer>();
dfs_path(result, cur_result, root, sum);
return result;
}
private void dfs_path(List<List<Integer>> result, List<Integer> cur_result, TreeNode root, int sum) {
if(root == null) return;
cur_result.add(new Integer(root.val));
if(root.left == null && root.right == null && sum == root.val) {
result.add(new LinkedList(cur_result));
cur_result.remove(cur_result.size() - 1); //remove last one for steping back (backtracking)
return;
}
dfs_path(result, cur_result, root.left, sum - root.val);
dfs_path(result, cur_result, root.right, sum - root.val);
cur_result.remove(cur_result.size() - 1);
}
}
Stack 法二. 每个非空都先push，有左走左，没有就pop
