Tree

Key points

• Traversal:

  • pre-order, in-order, post-order

  • Two approaches: 1) DFS, 2) Iteration

• Divide & Conquer VS Traversal:

  • DC: one send left & right two people to get the result, and then do sth.

  • T: one with a notebook walk through the tree

• BST, Binary Search Tree:

  • in-order is a sorted list, important !

  • left < root < right, not duplicate

  • use TreeSet or TreeMap

• Tricks:

  • isLeaf(): root.left == null && root.right == null

  • every node: 1)root == null 2) root.left == null 3)root.right == null

• Binary Indexed Tree:

  • the sum of (0, i), in O(logn) time.

• Segment Tree:

  • sum/minimum in a range

Traverse

Pre-order

https://leetcode.com/problems/binary-tree-preorder-traversal/

Iterative

public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        List<Integer> res = new LinkedList<Integer>();
        TreeNode curr = root;

        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                res.add(curr.val);
                stack.push(curr);
                curr = curr.left;
            }
            TreeNode head = stack.pop();
            curr = head.right;
        }

        return res; 
    }
}

Recursive

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<Integer>();

        traverse(root, res);

        return res; 
    }

    private void traverse(TreeNode root, List<Integer> res) {
        if (root == null) return;

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

In-order

https://leetcode.com/problems/binary-tree-inorder-traversal/

Iterative

public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        List<Integer> res = new LinkedList<Integer>();
        TreeNode curr = root;

        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            TreeNode head = stack.pop();
            res.add(head.val);
            curr = head.right;
        }

        return res; 
    }
}

Recursive

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<Integer>();

        traverse(root, res);

        return res; 
    }

    private void traverse(TreeNode root, List<Integer> res) {
        if (root == null) return;

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

Post-order

https://leetcode.com/problems/binary-tree-postorder-traversal/

Iterative

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        LinkedList<Integer> res = new LinkedList<Integer>();
        TreeNode curr = root;

        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                res.addFirst(curr.val); // Revered of pre-order
                stack.push(curr);
                curr = curr.right; // Revered of pre-order
            }
            TreeNode head = stack.pop();
            curr = head.left; // Revered of pre-order
        }

        return res; 
    }
}

Recursive

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<Integer>();

        traverse(root, res);

        return res; 
    }

    private void traverse(TreeNode root, List<Integer> res) {
        if (root == null) return;

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

Reference: https://discuss.leetcode.com/topic/30632/preorder-inorder-and-postorder-iteratively-summarization

Serialization and deserialization

https://leetcode.com/problems/find-duplicate-subtrees https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/ https://leetcode.com/problems/serialize-and-deserialize-bst https://leetcode.com/problems/construct-string-from-binary-tree https://leetcode.com/problems/construct-binary-tree-from-string

DFS or BFS?

BFS: level

• 662-Maximum Width of Binary Tree

DFS: go through a path

• 437-Path Sum III

• 687-Longest Univalue Path

Common law

性质1：二叉树第i层上的结点数目最多为 2{i-1} (i≥1)。
性质2：深度为k的二叉树至多有2{k}-1个结点(k≥1)。
性质3：包含n个结点的二叉树的高度至少为log2 (n+1)。
性质4：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。

Array -> Complete Binary Tree: parent i, left 2i+1, right 2i+2

Types of Binary Tree

• Full Binary Tree

• Complete Binary Tree

• Binary Search Tree: left < root < right

  use TreeSet to implement BST: https://leetcode.com/problems/contains-duplicate-iii. TreeSet is implemented by Black-Red Tree, self balanced. insert,delete, search in O(logN) complexity.

• AVL Tree: |left height - right height| <= 1

• Heap: Max Heap, Min Heap. Heap is complete binary tree.

Priority Queue is a Heap, implemented using an Array object[]. More details about heapify: https://jaywinhuang.gitbooks.io/leetcode/content/mySolutions/023-merge-k-sorted-lists.html

Segment Tree

• the leaves are values of nums

https://leetcode.com/problems/range-sum-query-mutable/description/

ac2: Segment Tree

more intuitive, yet more code. Notice: use divide and conquer, no need to care about the mid point unless building the tree.

class NumArray {

    class SegTreeNode{
        int start, end, sum;
        SegTreeNode left, right;
        public SegTreeNode(int start, int end){
            this.start = start;
            this.end = end;
            sum = 0;
        }
    }

    SegTreeNode root;

    public NumArray(int[] nums) {
        root = build(nums, 0, nums.length-1);
    }
    private SegTreeNode build(int[] nums, int start, int end) {
        if (start < 0 || end >= nums.length || start > end) return null;

        int mid = start + (end - start) / 2;
        SegTreeNode node = new SegTreeNode(start, end);
        if (start == end) {
            node.sum = nums[start];
        } else {
            node.left = build(nums, start, mid);
            node.right = build(nums, mid+1, end);
            node.sum = node.left.sum + node.right.sum;
        }
        return node;
    }

    public void update(int i, int val) {
        update(root, i, val);
    }
    private void update(SegTreeNode root, int i, int val) {
        if (i < root.start || i > root.end) return; // out of range
        if (root.start == root.end) {
            root.sum = val; // leaf, sum = nums[i]
            return;
        }

        // divide and conquer
        update(root.left, i, val);
        update(root.right, i, val);
        root.sum = root.left.sum + root.right.sum;  
    }

    public int sumRange(int i, int j) {
        return sumRange(root, i, j);
    }
    private int sumRange(SegTreeNode root, int i, int j) {
        if (i > root.end || j < root.start) return 0; // out of range
        if (i <= root.start && root.end <= j) return root.sum;  // current node within range, return value

        // divide and conquer
        int res = 0;
        res += sumRange(root.left, i, j);
        res += sumRange(root.right, i, j);
        return res;
    }

}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(i,val);
 * int param_2 = obj.sumRange(i,j);
 */

Binary Indexed Tree

https://leetcode.com/problems/range-sum-query-mutable/description/ https://leetcode.com/problems/range-sum-query-2d-mutable/description/

ac1: Binary Indexed Tree

careful: bit.length = nums.length + 1; so need to do i++ in methods

class NumArray {
    int[] bit;
    int[] nums;

    public NumArray(int[] nums) {
        this.nums = nums;
        bit = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            int val = nums[i];
            nums[i] = 0;
            update(i, val);
        }
    }

    public void update(int i, int val) {
        // index + last '1' bit 
        int diff = val - nums[i];
        nums[i] = val;

        i++;
        while (i < bit.length) {
            bit[i] += diff;
            i += i & (-i);
        }
    }

    private int getSum(int i) {
        // index - last '1' bit 
        i++;
        int res = 0;
        while (i > 0) {
            res += bit[i];
            i -= i & (-i);
        }
        return res;
    }

    public int sumRange(int i, int j) {
        return getSum(j) - getSum(i-1);
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(i,val);
 * int param_2 = obj.sumRange(i,j);
 */

https://leetcode.com/problems/reverse-pairs/description/ https://leetcode.com/problems/count-of-smaller-numbers-after-self https://leetcode.com/problems/count-of-range-sum

Binary Search Tree

in-order asecending https://leetcode.com/problems/validate-binary-search-tree/description/ https://leetcode.com/problems/kth-smallest-element-in-a-bst/

Divide & Conquer

get result from children, then do something

https://leetcode.com/problems/longest-univalue-path/description/ https://leetcode.com/problems/count-univalue-subtrees/description/ https://leetcode.com/problems/subtree-of-another-tree/description/