Powered by GitBook

Preorder Traversal:

while (!stack.isEmpty || curr != null)：表示只要 stack里有数或者 curr 非空就有可能有下一个node
当且仅当都为空时 end loop

    // Version 1: stack
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        // write your code here
        ArrayList<Integer> rst = new ArrayList<>();

        if (root == null) {
            return rst;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;

        while (!stack.isEmpty() || curr != null) {

            if (curr != null) {
                rst.add(curr.val);
                stack.push(curr);
                curr = curr.left;
            } else {
                curr = stack.pop();
                curr = curr.right;
            }
        }

        return rst;
    }

//Version 2: Divide & Conquer
public class Solution {
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        // null or leaf
        if (root == null) {
            return result;
        }

        // Divide
        ArrayList<Integer> left = preorderTraversal(root.left);
        ArrayList<Integer> right = preorderTraversal(root.right);

        // Conquer
        result.add(root.val);
        result.addAll(left);
        result.addAll(right);
        return result;
    }
}

//Version 3: Traverse DFS
public class Solution {
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        traverse(root, result);
        return result;
    }
    // 把root为跟的preorder加入result里面
    private void traverse(TreeNode root, ArrayList<Integer> result) {
        if (root == null) {
            return;
        }

        result.add(root.val);
        traverse(root.left, result);
        traverse(root.right, result);
    }
}

Inorder Traversal:

    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> rst = new ArrayList<>();

        if (root == null) return rst;

        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;

        // 表示只要 stack里有数 或者 curr 非空 就有可能有下一个node
        while (!stack.isEmpty() || curr != null) {
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            } else {
                curr = stack.pop();
                rst.add(curr.val);
                curr = curr.right;
            }
        }

        return rst;
    }

Postorder Traversal:

Two stack
https://www.youtube.com/watch?v=qT65HltK2uE

public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<Integer> rst = new LinkedList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode curr = root;

    while(!stack.isEmpty() || curr != null) {
        if(curr != null) {
            stack.push(curr);
            result.addFirst(curr.val);  // Reverse the process of preorder
            curr = curr.right;             // Reverse the process of preorder
        } else {
            curr node = stack.pop();
            curr = node.left;           // Reverse the process of preorder
        }
    }
    return result;
}

    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        // write your code here
        ArrayList<Integer> rst = new ArrayList<>();
        if (root == null) return rst;

        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();    // also can be linkedlist, use addFirst, then no need to reverse.

        stack1.push(root);

        while (!stack1.isEmpty()) {
            TreeNode curr = stack1.pop();
            TreeNode left = curr.left;
            TreeNode right = curr.right;
            if (left != null) stack1.push(left);
            if (right != null) stack1.push(right);
            stack2.push(curr);
        }

        while (!stack2.isEmpty()) {
            rst.add(stack2.pop().val);
        }

        return rst;
    }

BFS:

    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        // write your code here
        ArrayList<ArrayList<Integer>> rst = new ArrayList<>();

        if (root == null) {
            return rst;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            ArrayList<Integer> level = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            rst.add(level);
        }

        return rst;
    }

Maximum Depth of Binary Tree:

divide and conquer

    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = maxDepth(root.left);
        int right = maxDepth(root.right);

        return Math.max(right, left) + 1;
    }

dfs traversal

    int depth;
    public int maxDepth(TreeNode root) {
        depth = 0;
        dfs(root, 1);
        return depth;
    }

    private void dfs(TreeNode root, int currDepth) {
        if (root == null) return;

        depth = Math.max(currDepth, depth);

        dfs(root.left, currDepth + 1);
        dfs(root.right, currDepth + 1);
    }

Balanced Binary Tree:

// Version 1: with ResultType, divide and conquer
class ResultType {
    public boolean isBalanced;
    public int maxDepth;
    public ResultType(boolean isBalanced, int maxDepth) {
        this.isBalanced = isBalanced;
        this.maxDepth = maxDepth;
    }
}

public class Solution {
    public boolean isBalanced(TreeNode root) {
        return helper(root).isBalanced;
    }

    private ResultType helper(TreeNode root) {
        if (root == null) {
            return new ResultType(true, 0);
        }

        ResultType left = helper(root.left);
        ResultType right = helper(root.right);

        // subtree not balance
        if (!left.isBalanced || !right.isBalanced) {
            return new ResultType(false, -1);
        }

        // root not balance
        if (Math.abs(left.maxDepth - right.maxDepth) > 1) {
            return new ResultType(false, -1);
        }

        return new ResultType(true, Math.max(left.maxDepth, right.maxDepth) + 1);
    }
}

// Version 2: without ResultType
public class Solution {
    public boolean isBalanced(TreeNode root) {
        return maxDepth(root) != -1;
    }

    private int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        if (left == -1 || right == -1 || Math.abs(left-right) > 1) {
            return -1;
        }
        return Math.max(left, right) + 1;
    }
}

Path Sum ii

root -> leaf, not root -> any

public List<List<Integer>> pathSum(TreeNode root, int sum) {

        List<List<Integer>> rst = new ArrayList<>();
        List<Integer> list = new ArrayList<>();

        dc(rst, list, sum, root);        
        return rst;
    }

    private void dc(List<List<Integer>> rst, List<Integer> list, int target, TreeNode node) {

        if (node == null) return;

        list.add(node.val);
        if (node.val == target && node.left == null && node.right == null) {
            rst.add(new ArrayList<>(list));
        }

        dc(rst, list, target - node.val, node.left);
        dc(rst, list, target - node.val, node.right);

        list.remove(list.size() - 1);    
    }

LCA

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
        if (root == null || root.val == A.val || root.val == B.val) {
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left, A, B);
        TreeNode right = lowestCommonAncestor(root.right, A, B);

        if (left != null && right != null) {
            return root;
        } else if (left != null) {
            return left;
        } else if (right != null) {
            return right;
        } else {
            return null;
        }
    }

LCA in BST

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if (root == null) return null;

        if (p.val > root.val && q.val > root.val) return lowestCommonAncestor(root.right, p, q);
        if (p.val < root.val && q.val < root.val) return lowestCommonAncestor(root.left, p, q);

        return root;        
    }

Binary Tree Zigzag Level Order Traversal

use two stacks, cf: one queue
or same as BFS but Collections.reverse odd level

Binary Tree Level Order Traversal II

result put in a stack, then reverse output
or use linkedlist, addFirst()

Binary Tree Maximum Path Sum ii:

root to any

public int maxPathSum2(TreeNode root) {  
    if (root == null) {  
        return 0;  
    }  
    return root.val + Math.max(0, Math.max(maxPathSum2(root.left), maxPathSum2(root.right)));  
}

Binary Tree Maximum Path Sum

any to any

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: An integer.
     */
    private class ResultType {
        int singlePath;
        int maxPath;

        ResultType(int singlePath, int maxPath) {
            this.singlePath = singlePath;
            this.maxPath = maxPath;
        }

    } 

    public int maxPathSum(TreeNode root) {
        // write your code here
        ResultType rst = dfs(root);
        return rst.maxPath;
    }

    private ResultType dfs(TreeNode root) {

        if (root == null) {
            return new ResultType(0, Integer.MIN_VALUE);
        }

        ResultType left = dfs(root.left);
        ResultType right = dfs(root.right);

        int singlePath = Math.max(left.singlePath, right.singlePath) + root.val;
        singlePath = Math.max(singlePath, 0);

        // not + root.val b/c plus 的可能为－
        // maxPath 表示有拐的
        int maxPath = Math.max(left.maxPath, right.maxPath);
        maxPath = Math.max(maxPath, left.singlePath + right.singlePath + root.val);

        return new ResultType(singlePath, maxPath);
    } 
}

Binary Tree Path:

divide and conquer

    public List<String> binaryTreePaths(TreeNode root) {
        // Write your code here
        List<String> list = new ArrayList<>();
        if (root == null) return list;

        // divide 
        List<String> left = binaryTreePaths(root.left);
        List<String> right = binaryTreePaths(root.right);

        // conquer
        if (left.size() == 0 && right.size() == 0) {
            list.add("" + root.val);
        }

        for (String singlePath : left) {
            list.add(root.val + "->" + singlePath);
        }

        for (String singlePath : right) {
            list.add(root.val + "->" + singlePath);
        }

        return list;
    }

backtracking

    public List<String> binaryTreePaths(TreeNode root) {
        // Write your code here
        List<String> rst = new ArrayList<>();
        if (root == null) return rst;

        dfs(root, rst, new StringBuilder());
        return rst;
    }

    private void dfs(TreeNode root, List<String> rst, StringBuilder sb) {
        if (root == null) {
            return;
        }

        int currLength = sb.length();
        sb.append(root.val);

        if (root.left == null && root.right == null) {
            rst.add(new String(sb));
            sb.setLength(currLength);
            return;
        }

        sb.append("->");
        dfs(root.left, rst, sb);
        dfs(root.right, rst, sb);

        sb.setLength(currLength);

        return;
    }

Path Sum - exists:

divide and conquer

    public boolean hasPathSum(TreeNode root, int sum) {

        if (root == null) return false;        
        if (sum == root.val && root.left == null && root.right == null) return true;

        boolean left = hasPathSum(root.left, sum - root.val);
        boolean right = hasPathSum(root.right, sum - root.val);

        return left || right;        
    }

Path Sum - all paths:

backtracking

public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {

        List<List<Integer>> rst = new ArrayList<>();
        List<Integer> list = new ArrayList<>();

        dfs(rst, list, sum, root);        
        return rst;
    }

    private void dfs(List<List<Integer>> rst, List<Integer> list, int target, TreeNode node) {

        if (node == null) return;

        list.add(node.val);
        if (node.val == target && node.left == null && node.right == null) {
            rst.add(new ArrayList<>(list));
        }

        dfs(rst, list, target - node.val, node.left);
        dfs(rst, list, target - node.val, node.right);

        list.remove(list.size() - 1);    
    }
}

LCS:

dfs

public class Solution {
    int max = Integer.MIN_VALUE;;
    public int longestConsecutive(TreeNode root) {
        if (root == null) return 0;

        dfs(root, 0, root.val);
        return max;
    }

    private void dfs(TreeNode root, int count, int target) {

        if (root == null) return;
        if (target == root.val) {
            count++;
        } else {
            count = 1;
        }

        max = Math.max(count, max);

        dfs(root.left, count, root.val + 1);
        dfs(root.right, count, root.val + 1);
    }
}

divide conquer
can not write as:
- test case: [ 1, 2, 2, 3, [10~100]]
- if ((root.left != null) && (root.val - root.left.val == -1))
```
left = left + 1;  
```
  if ((root.right !=null) && (root.val - root.right.val == -1))
```
right = right + 1;
```
  return Math.max(left, right);

public int longestConsecutive(TreeNode root) {
    if(root==null) return 0;
    return Helper(root, 1, root.val);
}

public int Helper(TreeNode root, int count, int val){
    if(root==null) return count;
    count = (root.val - val == 1)?count+1:1;
    int left = Helper(root.left, count, root.val);
    int right = Helper(root.right, count, root.val);
    return Math.max(Math.max(left, right), count);
}

Flatten Binary Tree to LinkedList

// Version 1: Traverse
public class Solution {
    private TreeNode lastNode = null;

    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }

        if (lastNode != null) {
            lastNode.left = null;
            lastNode.right = root;
        }

        lastNode = root;
        TreeNode right = root.right;
        flatten(root.left); // 因为这一步之后 root.right位置有变 所以需要存盘当前的right
        flatten(right);
    }
}

// version 2: Divide & Conquer
public class Solution {
    /**
     * @param root: a TreeNode, the root of the binary tree
     * @return: nothing
     */
    public void flatten(TreeNode root) {
        helper(root);
    }

    // flatten root and return the last node
    private TreeNode helper(TreeNode root) {
        if (root == null) {
            return null;
        }

        TreeNode leftLast = helper(root.left);
        TreeNode rightLast = helper(root.right);

        // connect leftLast to root.right
        if (leftLast != null) {
            leftLast.right = root.right;
            root.right = root.left;
            root.left = null;
        }

        if (rightLast != null) {
            return rightLast;
        }

        if (leftLast != null) {
            return leftLast;
        }

        return root;
    }
}

// version 3: Non-Recursion
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: a TreeNode, the root of the binary tree
     * @return: nothing
     */
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.empty()) {
            TreeNode node = stack.pop();
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }

            // connect 
            node.left = null;
            if (stack.empty()) {
                node.right = null;
            } else {
                node.right = stack.peek();
            }
        }
    }
}

identical binary tree

    public boolean isIdentical(TreeNode node1, TreeNode node2) {
        // Write your code here
        if (node1 == null && node2 == null) {
            return true;
        }

        if (node1 == null || node2 == null) {
            return false;
        }

        if (node1.val != node2.val) {
            return false;
        }

        return isIdentical(node1.left, node2.left) && isIdentical(node2.right, node1.right);
    }

symmetric binary tree

    public boolean isSymmetric(TreeNode root) {
        // Write your code here
        if (root == null) {
            return true;
        }
        return check(root.left, root.right);
    }

    private boolean check(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) {
            return true;
        }
        if (root1 == null || root2 == null) {
            return false;
        }
        if (root1.val != root2.val) {
            return false;
        }
        return check(root1.left, root2.right) && check(root1.right, root2.left);
    }

results matching ""

No results matching ""