1/15, Validate 树类型

验证树是否具有某种性质。比如，Balanced, BST, Complete 等等。

BST
Balanced
Identical/Tweaked Identical/Subtree
Complete
Symmetric
invert binary tree

都需要对树遍历，遍历的方式不同，有DFS和BFS，很多是DFS。

知道定义

别搞错要validate什么，还有写之前先define树节点结构体TreeNode()

用什么方法？

一个问题的迭代(iterative)和递归(recursive)解法最好都要掌握。通常先用迭代，再用递归。

时间复杂度

如果程序会遍历一整棵有n个节点的树，且每个节点至多遍历一次，O(n) on worst/average.

空间复杂度

对于tree的recursive implementation，space complexity is the max depth of the recursion tree - O(max_h).

两种解法的比较

迭代，用循环加stack，来simulate递归执行中系统给程序分配的栈空间，能防止stack overflow。

在stack里加入一个包含节点，最小下限，和最大上限的tuple，每次迭代对当前pop出的节点值进行判定。

递归，要想到问题的分解，和问题的出口。思路和迭代一致。注意要分别对返回的左右节点结果进行判断，如果任何一边不满足，就返回False。

12/14复习注，是一个尾递归，注意dfs()和主函数是如何把问题拆解的。由于dfs在第一个出口处要检查node.value，所以在每次dfs的拆解之前，都要check有没有左右节点。

2/1复习，递归解法，dfs也可以check node是否为empty，就不用再check if left/right node exist，但会产生额外function calls。

2/16 实际处理问题时，记住迭代是递归的优化。看到很多面试中都会问，如果输入数据量很大时，怎么处理？

遇到这个问题，通常是由于先写了递归解法，而递归的缺点就是当处理的数据很大时，function call可能会指数型增长，就会造成stack overflow，然后program crash。所以，优化方法就是转迭代，避免implicit function call。

Unique Binary Search Tree

First note that dp[k] represents the number of BST trees built from 1....k;

Then assume we have the number of the first 4 trees: dp[1] = 1 ,dp[2] =2 ,dp[3] = 5 , how do we get dp[5] based on these four numbers is the core problem here.

The essential process is: to build a tree, we need to pick a root node, then we need to know how many possible left sub trees and right sub trees can be held under that node, finally multiply them.

To build a tree contains {1,2,3,4}. First we pick 1 as root, for the left sub tree, there are none; for the right sub tree, we need count how many possible trees are there constructed from {2,3,4}, apparently it's the same number as {1,2,3}. So the total number of trees under "1" picked as root is dp[0] * dp[3] = 5. (assume dp[0] =1). Similarly, root 2 has dp[1]*dp[2] = 2 trees. root 3 has dp[2]*dp[1] = 2, root 4 has dp[3]*dp[1]= 5. Finally sum the up and it's done.

Now, we may have a better understanding of the dp[k], which essentially represents the number of BST trees with k consecutive nodes. It is used as database when we need to know how many left sub trees are possible for k nodes when picking (k+1) as root.

the double loop solution:

public class Solution {
  public int numTrees(int n) {
    int[] G = new int[n + 1];
    G[0] = 1;
    G[1] = 1;

    for (int i = 2; i <= n; ++i) {
      for (int j = 1; j <= i; ++j) {
        G[i] += G[j - 1] * G[i - j];
      }
    }
    return G[n];
  }
}

To be concise, we can use memorization to store the intermidiate result during the process.

class Solution {
    Map<Integer, Integer> map;
    public int numTrees(int n) {
        map = new HashMap<>();

        return helper(n);
    }

    private int helper(int m) {
        if (map.containsKey(m)) {
            return map.get(m);
        }

        // base case
        if (m == 0 || m == 1) {
            map.put(m, 1);
            return 1;
        }

        // recursive case
        int total = 0;
        for (int i = 1; i <= m; ++i) {
            total += (helper(i - 1) * helper(m - i));
        }

        // DP memorization
        map.put(m, total);

        return total;
    }
}

Follow up: print all the nodes

based on the explanation above, we know that we can use recursive method to solve the problem. To get the TreeNode, we need specific node value instead of node number. So we can maintain a range of the sequence that we build the tree from.

public List<TreeNode> generateTrees(int n) {
    if (n == 0) {
        return new ArrayList<TreeNode>();
    }
    return helper(1, n);
}

private List<TreeNode> helper(int low, int high) {
    List<TreeNode> list = new ArrayList<>();

    if (low > high) {
        list.add(null);
        return list;
    }

    for (int i = low; i <= high; ++i) {

        List<TreeNode> left = helper(low, i - 1);
        List<TreeNode> right = helper(i + 1, high);

        for (TreeNode j : left) {
            for (TreeNode k : right) {
                TreeNode root = new TreeNode(i);
                root.left = j;
                root.right = k;
                list.add(root);
            }
        }
    }

    return list;
}

Balanced Binary Tree

这道题要想到需要哪些变量。每一个level中左右节点的高度，以及判断左右子树的高度差不大于1，子树的高度取决于max(left, right)+1。-1代表这个不是一个balanced BST。迭代不适用，因为需要从底部开始计算高度。dd

递归 ✔️

class Solution {
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }

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

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

        if (left == -1 || right == -1 || Math.abs(left - right) > 1) return -1;

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

跟上一题一样，也是尾递归。要注意的地方是，对左右子树是否balance的判断。因为如果其中一个已经是不balanced，应该直接返回False，否则有可能得到False Positive。

Tweaked Identical Binary Tree

Problem: Check two given binary trees are identical or not. Assuming any number of tweaks are allowed. A tweak is defined as a swap of the children of one node in the tree

这道题是same tree的加强版。判断两棵树是否tweaked一样，要满足两树在每一个level节点顺序可能相反，但parent和children的相对位置不变，就是你大爷还是你大爷。跟非tweaked的区别，非tweaked必须满足在每一level，节点位置是固定且一样的。

递归 ✔️

public boolean isTweakedIdentical(TreeNode a, TreeNode b) {

    if (a == null && b == null) {
        return true;
    }

    if (a == null || b == null) {
        return false;
    }

    if (a.val != b.val) {
        return false;
    }

    // divide 
    // note: 题目中说的是经过若干次扭转后可以等价，所以不要忘记考虑完全identical的情况，某一个节点的左右子树翻转一次对称，反转两次还原
    boolean nontweak = isTweakedIdentical(a.left, b.left) && isTweakedIdentical(a.right, b.right);
    boolean tweak = isTweakedIdentical(a.right, b.left) && isTweakedIdentical(a.left, b.right);

    // conquer
    return nontweak || tweak;
}

递归的出口是当两个节点都为空时返回True。重点是递归的分解，当两个节点都非空时才分解。Tweak的话就是在非tweak的基础上多条or判断。

12/30复习，和symmetric tree区分一下，做法一个是DFS，一个BFS。note: symmetric tree 可以用BFS来做，注意一下。

Symmetric Binary Tree

判断一棵树是不是a mirror of itself。get rid of the root level, start checking from second level binary tree. Still two leveled binary tree structure.

recursive solution: preferred.

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;

        return isSymmetric(root.left, root.right);
    }

    private boolean isSymmetric(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;

        return left.val == right.val && isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
    }
}

iterative solution:

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);

        while (!queue.isEmpty()) {
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();

            if (left == null && right == null) continue;
            if (left == null || right == null) return false;
            if (left.val != right.val) return false;

            queue.offer(left.left);
            queue.offer(right.right);
            queue.offer(left.right);
            queue.offer(right.left);
        }
        return true;
    }
}

关键是判断每个level中，两两三元小子树是不是对称，用recursive做比较直观。

例子： a d

： b c e f

we need to check whether (a.val == d.val && isSym(b, f) && isSym(c, e))

3/9补充，可以用deque做，和level order traversal一回事。

Invert Binary Tree

classic tree problem that is best-suited for a recursive approach. The inverse of an empty tree is the empty tree. The inverse of a tree with root rr, and subtrees right and left, is a tree with root rr, whose right subtree is the inverse of left, and whose left subtree is the inverse of right.

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        TreeNode right = invertTree(root.right);
        TreeNode left = invertTree(root.left);
        root.left = right;
        root.right = left;

        return root;
    }
}

Time complexity is O(n), jSince each node in the tree is visited only once, the time complexity is O(n), where nn is the number of nodes in the tree. We cannot do better than that, since at the very least we have to visit each node to invert it.

Because of recursion, O(h) function calls will be placed on the stack in the worst case, where hh is the height of the tree. Because h∈O(n), the space complexity is O(n)

Complete Binary Tree

要判断一棵树是不是complete，这棵树要满足1)按level order从左到右能依次填满，2)除了最底层，上面每个level都必须是满的。

A complete tree - all levels except the last one are completely full, and if the last level isn't totally full, nodes are added from left to right.

所以解这道题要用BFS来做。举题目中的反例，遍历完这棵树后，得到stack=[1,2,3,N,4,N,N]，再按从后往前的顺序把空节点弹出，直到第一个非空节点4，得到[1,2,3,N,4]。这时的stack里因为还有空节点，就说明至少不满足两个判定条件中的一个。

关键在如何遍历才能得到所有的节点(包括空节点)，还要按level order排列。每一个level的节点要从左到右遍历完，才能访问下个level的节点。

时间复杂度O(n)，extra O(n) space。

iterative solution: preferred 

public class CompleteBTree {

    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int n) {
            val = n;
            left = null;
            right = null;
        }
    }

    public boolean isCompleteBT(TreeNode root) {
        if (root == null) {
            return true;
        }

        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean flag = false;

        while (!queue.isEmpty()) {
            TreeNode temp = queue.poll();

            if (temp.left != null) {
                if (flag == true) return false;
                queue.offer(temp.left);
            } else {
                flag = true;       // if temp.left == null, means it is possible to find a complete BTree 
                                   // if and only if there is no subsequent node that need to push to the queue
            }

            if (temp.right != null) {
                if (flag == true) return false;
                queue.offer(temp.right);
            } else {
                flag = true;
            }
        }
        return true;
    }
}

recursive solution: 

public class CompleteBTree {

    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int n) {
            val = n;
            left = null;
            right = null;
        }
    }

    private int countNodes(TreeNode root) {

        if (root == null) {
            return 0;
        }
        return (1 + countNodes(root.left) + countNodes(root.right));
    }

    private boolean isComplete(TreeNode root, int index, int num) {
        // an empty tree is complete
        if (root == null) {
            return true;
        }
        // tree is not complete if index assigned to current node is more than number of nodes in tree.
        if (index >= num) {
            return false;
        }

        // recur for left and right subtrees
        return (isComplete(root.left, 2 * index + 1, num) 
            && (isComplete(root.right, 2 * index + 2, num));
    }

    private boolean isComplete(TreeNode root) {
        return isComplete(root, 0, countNodes(root));
    }
}

note: in the array representation of complete binary tree, if the parent node is assigned an index of 'i', and left child gets assigned an index of '2*i + 1', while the right child is assigned an index of '2*i + 2'. Similarly, if we know the index of one child as i, we can get the index of its parent as (i - 1)/2.

refer: https://www.geeksforgeeks.org/check-if-a-given-binary-tree-is-complete-tree-or-not/ https://www.geeksforgeeks.org/check-whether-binary-tree-complete-not-set-2-recursive-solution/

Validate