230. Kth Smallest Element in a BST

https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/
    int kthSmallest(TreeNode* root, int k) {
        int res;
        inOrder(root, k, res);
        return res;
    }
    void inOrder(TreeNode* node, int& k, int& res) {
        if(!node) return;
        if(k>0) inOrder(node->left, k, res);
        k--;
        if(k ==0) { res = node->val; return; }
        if(k>0) inOrder(node->right, k, res);
    }

144. Binary Tree Preorder Traversal

https://leetcode.com/problems/binary-tree-preorder-traversal/description/
Solution 1. Recursion
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        preOrder(root, res);
        return res;
    }
    void preOrder(TreeNode* node, vector<int>& res) {
        if(!node) return;
        res.push_back(node->val);
        preOrder(node->left, res);
        preOrder(node->right, res);
    }
Solution 2. Iteration
    vector<int> preorderTraversal(TreeNode* root) {
        if(!root) return {};
        vector<int> res;
        TreeNode* node;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()) {
            node = st.top();
            res.push_back(node->val);
            st.pop();
            if(node->right) st.push(node->right);
            if(node->left) st.push(node->left);
        }
        return res;
    }

421. Maximum XOR of Two Numbers in an Array

https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/description/
Solution 1. Get the max XOR for each num using TRIE searching after the tree is built.
Solution 2. Search the tree after the tree is built.
class Solution {
    struct TreeNode {
        TreeNode* l;
        TreeNode* r;
        TreeNode(): l(nullptr), r(nullptr) {};
    };
public:
    int findMaximumXOR(vector<int>& nums) {
        if(nums.size()<2) return 0;
        int b = 30;
        TreeNode* root = getTree(nums, b), *node = root;
        while(node && !(node->l && node->r)) {
            b--;
            if(node->l) node = node->l;
            else node = node->r;
        }
        if(b==-1) return 0;
        int res = 0;
        dfs(node->l, node->r, b, res, 1<<b);
        return res;
    }
    void dfs(TreeNode* nl, TreeNode* nr, int b, int& res, int s) {
        if(b==-1) {
            if(s>res) res = s;
            return;
        }
        if(!nl || !nr) return;
        b--;
        if(nl->l && nr->r || nl->r && nr->l) {
            dfs(nl->l, nr->r, b, res, s|(1<<b));
            dfs(nl->r, nr->l, b, res, s|(1<<b));
        }
        else {
            dfs(nl->l, nr->l, b, res, s);
            dfs(nl->r, nr->r, b, res, s);
        }
    }
    TreeNode* getTree(vector<int>& nums, int b) {
        TreeNode* root = new TreeNode(), *node;
        for(int n : nums) {
            int k = 1<<b;
            node = root;
            while(k) {
                if(k&n) {
                    if(!node->r) node->r = new TreeNode();
                    node = node->r;
                }
                else {
                    if(!node->l) node->l = new TreeNode();
                    node = node->l;
                }
                k >>= 1;
            }
        }
        return root;
    }
};

623. Add One Row to Tree

https://leetcode.com/problems/add-one-row-to-tree/description/
    void add(TreeNode* node, const int& v, const int& d, int dep) {
        if(!node) return;
        if(d == dep){
            TreeNode* save;
           
            save = node->left;
            node->left = new TreeNode(v);
            node->left->left = save;
           
            save = node->right;
            node->right = new TreeNode(v);
            node->right->right = save;
            return;
        }
        add(node->left, v, d, dep+1);
        add(node->right, v, d, dep+1);
    }
    TreeNode* addOneRow(TreeNode* root, int v, int d) {
        if(d==1) {
            TreeNode* save = root;
            root = new TreeNode(v);
            root->left = save;
            return root;
        }
        add(root, v, d, 2);
        return root;
    }

94. Binary Tree Inorder Traversal

https://leetcode.com/problems/binary-tree-inorder-traversal/description/
Solution 1. Recursion.
    void inOrder(TreeNode*node, vector<int>& res) {
        if(!node) return;
        inOrder(node->left, res);
        res.push_back(node->val);
        inOrder(node->right, res);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        inOrder(root, res);
        return res;
    }
Solution 2. Iteration
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        TreeNode* node = root;
        while(!st.empty() || node) {
            if(node) {
                st.push(node);
                node = node->left;
            }
            else {
                node = st.top();
                st.pop();
                res.push_back(node->val);
                node = node->right;
            }
        }
        return res;
    }

655. Print Binary Tree

https://leetcode.com/problems/print-binary-tree/description/
Solution 1. Always think in the computer way. Figure out the repeating pattern.
    int height(TreeNode* node) {
        if(!node) return 0;
        int l = height(node->left), r = height(node->right);
        return max(l, r) + 1;
    }
    int width(TreeNode* node) {
        if(!node) return 0;
        int l = width(node->left), r = width(node->right);
        return max(l, r) * 2 + 1;
    }
    void print(TreeNode* node, vector<vector<string>>& res, int level, int l, int r) {
        if(!node) return;
        int mid = l + (r - l)/2;
        res[level][mid] = to_string(node->val);
        print(node->left, res, level+1, l, mid-1);
        print(node->right, res, level+1, mid+1, r);
    }
    vector<vector<string>> printTree(TreeNode* root) {
        int h = height(root);
        //int w = pow(2,h) - 1;
        int w = width(root);
        vector<vector<string>> res(h, vector<string> (w,""));
        print(root, res, 0, 0, w-1);
        return res;
    }
Solution 2. Convert location to index.
    void visit(TreeNode* node, vector<vector<pair<int,int>>>& t, int level, int idx) {
        if(!node) return;
        if(t.size()==level) t.push_back({});
        t[level].push_back({idx, node->val});
        visit(node->left, t, level+1, 2*idx);
        visit(node->right, t, level+1, 2*idx+1);
    }
    vector<vector<string>> printTree(TreeNode* root) {
        vector<vector<pair<int,int>>> t;
        visit(root, t, 0, 0);
        int r = t.size();
        int c = pow(2,r) - 1;
        vector<vector<string>> res(r, vector<string> (c, ""));

        for(int i=r-1; i>=0; i--) {
            int k0 = pow(2, r-i-1) - 1;
            int dk = pow(2, r-i);
            for(int j=0; j<t[i].size(); j++) {
                int k = k0 + dk*t[i][j].first;
                res[i][k] = to_string(t[i][j].second);
            }
        }
        return res;
    }

508. Most Frequent Subtree Sum

https://leetcode.com/problems/most-frequent-subtree-sum/description/
    int postOrder(TreeNode* node, unordered_map<int,int>& mp) {
        if(!node) return 0;
        int l = postOrder(node->left, mp);
        int r = postOrder(node->right, mp);
        int s = l+r+node->val;
        mp[s]++;
        return s;
    }
    vector<int> findFrequentTreeSum(TreeNode* root) {
        if(!root) return {};
        unordered_map<int,int> mp;
        postOrder(root, mp);
        map<int,vector<int>> cnt2node;
        for(auto &m : mp) {
            cnt2node[m.second].push_back(m.first);
        }
        return (*cnt2node.rbegin()).second;
    }

687. Longest Univalue Path

    int len(TreeNode* node, int pa, int& mx) { // pa is the value of parent node
        if(!node) return 0;
        int l = len(node->left, node->val, mx);
        int r = len(node->right, node->val,mx);
        mx = max(mx, l+r);
        if(node->val == pa) return 1+max(l,r);
        else return 0;
    }
    int longestUnivaluePath(TreeNode* root) {
        if(!root) return 0;
        int mx = 0;
        // root doesn't have parent node, pick any value that is different
        len(root, root->val-1, mx);
        return mx;
    }

515. Find Largest Value in Each Tree Row

https://leetcode.com/problems/find-largest-value-in-each-tree-row/description/
Solution 1. Recursion.
    void levelOrder(TreeNode* node, vector<int>& res, int lev) {
        if(!node) return;
        if(res.size() == lev) res.push_back(node->val);
        else
            res[lev] = res[lev] > node->val ? res[lev] : node->val;
        levelOrder(node->left, res, lev+1);
        levelOrder(node->right, res, lev+1);
    }
    vector<int> largestValues(TreeNode* root) {
        vector<int> res;
        levelOrder(root, res, 0);
        return res;
    }
Solution 2. 
    vector<int> largestValues(TreeNode* root) {
        vector<int> res;
        if(!root) return res;
        queue<TreeNode*> q;
        q.push(root);
        q.push(nullptr);
        int mx = INT_MIN;
        while(!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            if(node == nullptr) {
                res.push_back(mx);
                mx = INT_MIN;
                if(!q.empty())
                    q.push(nullptr);
            }
            else {
                mx = mx>node->val ? mx : node->val;
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
        }
        return res;
    }

513. Find Bottom Left Tree Value

https://leetcode.com/problems/find-bottom-left-tree-value/description/
Solution 1
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        q.push(nullptr);
        int res;
        TreeNode* last = nullptr;
        while(q.size()>1) {
            if(last == nullptr) res = q.front()->val;
            last = q.front();
            q.pop();
            if(last == nullptr) {
                q.push(nullptr);
            }
            else {
                if(last->left) q.push(last->left);
                if(last->right) q.push(last->right);
            }
        }
        return res;
    }
Solution 2. Recursion
    void findLeft(TreeNode* node, int& mx, int& maxDep, int dep) {
        if(!node) return;
        if(maxDep < dep) {
            maxDep = dep;
            mx = node->val;
        }
        findLeft(node->left, mx, maxDep, dep+1);
        findLeft(node->right, mx, maxDep, dep+1);
    }
    int findBottomLeftValue(TreeNode* root) {
        int mx = root->val, maxDep = 0;
        findLeft(root, mx, maxDep, 0);
        return mx;
    }

654. Maximum Binary Tree

https://leetcode.com/problems/maximum-binary-tree/description/
Solution 1.
use a vector to keep part of tree nodes in decreasing order.
keep popping the vector until empty or a bigger number.
The bigger number (if exists) is current number's root, and the last popped number (if exist) is current number's right child and it is the parent of the number before last popped. 
push current number into the vector.
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        vector<TreeNode*> v;
        for(int n : nums) {
            TreeNode* node = new TreeNode(n);
            while(!v.empty() && v.back()->val<n) {
                node->left = v.back();
                v.pop_back();
            }
            if(!v.empty()) v.back()->right = node;
            v.push_back(node);
        }
        return v.front();
    }
Solution 2. Recursion
    TreeNode* construct(vector<int>& nums, int lo, int hi) {
        if(lo>hi) return nullptr;
        int mx = nums[lo], ix = lo;
        for(int i=lo+1; i<=hi;i++) if(nums[i]>mx) {
            mx = nums[i];
            ix = i;
        }
        TreeNode* node = new TreeNode(mx);
        node->left = construct(nums, lo, ix-1);
        node->right = construct(nums, ix+1, hi);
        return node;
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return construct(nums, 0, nums.size()-1);
    }

111. Minimum Depth of Binary Tree

https://leetcode.com/problems/minimum-depth-of-binary-tree/description/
Recursion, (9 ms)
    int minDepth(TreeNode* root) {
        if(!root) return 0;
        if(!root->left && !root->right) return 1;
        int l = minDepth(root->left);
        int r = minDepth(root->right);
        if(l == 0) return r+1;
        else if(r == 0) return l+1;
        else return min(l,r) + 1;
    }
or, (6 ms)
    void inOrder(TreeNode* node, int d, int& m) {
        if(!node) return;
        if(!node->left && !node->right) {
            m = min(m, d+1);
        }
        inOrder(node->left, d+1, m);
        inOrder(node->right, d+1, m);
    }
    int minDepth(TreeNode* root) {
        if(!root) return 0;
        int m = INT_MAX;
        inOrder(root, 0, m);
        return m;
    }

112. Path Sum

https://leetcode.com/problems/path-sum/description/

Recursion
    bool hasPathSum(TreeNode* root, int sum) {
        if(!root) return false;
        if(!root->left && !root->right && sum==root->val) return true;
        return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
    }
or,
    bool preOrder(TreeNode* node, int sum, int s) {
        s += node->val;
        if(!node->left && !node->right && s==sum) return true;
        return (node->left? preOrder(node->left, sum, s):false) ||
        (node->right? preOrder(node->right, sum, s):false);
    }
    bool hasPathSum(TreeNode* root, int sum) {
        if(!root) return false;
        return preOrder(root, sum, 0);
    }
Iteration
    bool hasPathSum(TreeNode* root, int sum) {
        if(!root) return false;
        stack<TreeNode*> st;
        stack<int> sm;
        st.push(root);
        sm.push(0);
        TreeNode* node;
        int sn = 0;
        while(!st.empty()) {
            node = st.top();
            st.pop();
            sn = sm.top() + node->val;
            sm.pop();
            if(!node->left && !node->right && sn==sum) return true;
            if(node->right) {st.push(node->right); sm.push(sn);}
            if(node->left) {st.push(node->left); sm.push(sn);}
        }
        return false;
    }

110. Balanced Binary Tree

https://leetcode.com/problems/balanced-binary-tree/description/
Solution: at each recursion step, check if left and right child are both balanced. At the same time check the maximum depth for each child.
    bool treeTrav(TreeNode* node, int& lev) {
        if(!node) return true;
        int levL = 0, levR = 0;
        if(treeTrav(node->left, levL) && treeTrav(node->right, levR))
            if(abs(levL-levR)>1) return false;
            else {
                lev = max(levL, levR) + 1;
                return true;
            }
        return false;
    }
    bool isBalanced(TreeNode* root) {
        int l = 0;
        return treeTrav(root, l);
    }

501. Find Mode in Binary Search Tree

https://leetcode.com/problems/find-mode-in-binary-search-tree/description/
Solution 1: In-order traversal
mx: max count of different values
cnt: counting the duplicates
preVal: previous checked value
    void inOrder(TreeNode* node, vector<int>& mode, int& mx, int& cnt, int& preVal) {
        if(!node) return;
        inOrder(node->left, mode, mx, cnt, preVal);
        if(cnt == 0) {
            cnt = 1;
            preVal = node->val;
        }
        else if(node->val == preVal) cnt++;
        else {
            if(mx == cnt) mode.push_back(preVal);
            else if(mx < cnt) {
                mx = cnt;
                mode.clear();
                mode.push_back(preVal);
            }
            preVal = node->val;
            cnt = 1;
        }
        inOrder(node->right, mode, mx, cnt, preVal);
    }
    vector<int> findMode(TreeNode* root) {
        vector<int> mode;
        if(!root) return mode;
        int mx = 0, cnt = 0, preVal;
        inOrder(root, mode, mx, cnt, preVal);
        if(mx < cnt) return {preVal};
        if(mx == cnt) mode.push_back(preVal);
        return mode;
    }
Solution 2. We can always do an in-order tree traversal and store the numbers in an array and then search for the mode.

101. Symmetric Tree

https://leetcode.com/problems/symmetric-tree/description/
Solution 1. Recursion.
    bool compareNodes(TreeNode* ln, TreeNode* rn) {
        if(!ln && !rn) return true;
        if(!ln || !rn || ln->val != rn->val) return false;
        return compareNodes(ln->left, rn->right) && compareNodes(ln->right, rn->left);
    }
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return compareNodes(root->left, root->right);
    }
Solution 2. Iteration. Need to take care of the case when ln->left =null and rn->left=null.
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        TreeNode *ln, *rn;
        stack<TreeNode*> lst, rst;
        lst.push(root->left);
        rst.push(root->right);
        while(!lst.empty() && !rst.empty()) {
            ln = lst.top();
            lst.pop();
            rn = rst.top();
            rst.pop();
            if(!ln && !rn) continue;
            if(!ln || !rn || ln->val != rn->val) return false;
            lst.push(ln->right);
            lst.push(ln->left);
            rst.push(rn->left);
            rst.push(rn->right);
        }
        if(!lst.empty() || !rst.empty()) return false;
        return true;
    }

235. Lowest Common Ancestor of a Binary Search Tree

Solution 1. Use property of binary search tree. (Don't forget to use the conditions of the problem!)
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(p->val < root->val && q->val < root->val)
            return lowestCommonAncestor(root->left, p, q);
        if(p->val > root->val && q->val > root->val)
            return lowestCommonAncestor(root->right, p, q);
        return root;
    }
Solution 2. Property of binary tree not used.
    int preOrder(TreeNode* node, const TreeNode* p, const TreeNode* q, TreeNode*& res) {
        if(!node || res) return 0;
        int n = 0;
        if(node == p || node == q) n = 1;
        n += preOrder(node->left, p, q, res);
        if(n == 2 && !res) res = node;
        n += preOrder(node->right, p, q, res);
        if(n == 2 && !res) res = node;
        return n;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* res = nullptr;
        preOrder(root, p, q, res);
        return res;
    }

437. Path Sum III

https://leetcode.com/problems/path-sum-iii/description/
Solution 0.  Recursion:
If the parent node is not used, the current node is the start of a new path. We should also start a new path from its leaves.
No matter the parent node is used or not, the current path should be continued through its leaves.
    void preOrder(TreeNode* node, int s, int& res, bool isParentUsed) {
        if(!node) return;
        if(s - node->val == 0) res++;
        // the current path continues through the leaves of the current node
        preOrder(node->left, s - node->val, res, true);
        preOrder(node->right, s - node->val, res, true);
        if(!isParentUsed) {
            // start a new path from the leaves of current node if parent is not used.
            // here s equal to the target "sum"
            preOrder(node->left, s, res, false);
            preOrder(node->right, s, res, false);
        }
    }
    int pathSum(TreeNode* root, int sum) {
        if(!root) return 0;
        int res = 0;
        preOrder(root, sum, res, false);
        return res;
    }
Solution 1. Do recursion sum from root to a node, increase path numbers if sum is equal to target. Then do a recursion for subtrees.
    int sumFromNode(TreeNode* node, int sum, int s) {
        if(!node) return 0;
        s += node->val;
        return (s == sum)
            + sumFromNode(node->left, sum, s)
            + sumFromNode(node->right, sum, s);
    }
    int pathSum(TreeNode* root, int sum) {
        if(!root) return 0;
        return sumFromNode(root, sum, 0)
            + pathSum(root->left, sum)
            + pathSum(root->right, sum);
    }
or,

107. Binary Tree Level Order Traversal II

https://leetcode.com/problems/binary-tree-level-order-traversal-ii/description/
Solution 1. Recursive level traversal. Need to add a {} to res to increase res.size() when starting a new level, otherwise res[level] causes index error.
    void levelOrder(TreeNode* node, vector<vector<int>>& res, int level) {
        if(!node) return;
        if(level == res.size()) res.push_back({});
        res[level].push_back(node->val);
        levelOrder(node->left, res, level+1);
        levelOrder(node->right, res, level+1);
    }
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> res;
        levelOrder(root, res, 0);
        reverse(res.begin(), res.end());
        return res;
    }
Solution 2. Push each level to a queue. Use nullptr as a separator between levels.
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> q;
        TreeNode* node;
        q.push(root);
        q.push(nullptr);
        while(!q.empty()) {
            vector<int> level;
            while(node = q.front()){
                q.pop();
                level.push_back(node->val);
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            q.pop();
            q.push(nullptr);
            if(level.empty()) break;
            res.insert(res.begin(),level);
        }
        return res;
    }

572. Subtree of Another Tree

https://leetcode.com/problems/subtree-of-another-tree/description/
Solution 1. Compare s to t, if they are not identical, then compare subtrees of s to t.
    bool isIdentical(TreeNode*s, TreeNode* t) {
        if(!s && !t) return true;
        if(!s || !t) return false;
        if(s->val != t->val) return false;
        return isIdentical(s->left, t->left) && isIdentical(s->right, t->right);
    }
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if(!t) return true;
        if(!s) return false;
        if(isIdentical(s, t)) return true;
        return isSubtree(s->left, t) || isSubtree(s->right, t);
    }
Solution 1.1. Only compare t to the subtrees of s that have same depth as t.
class Solution {
    vector<TreeNode*> vd;
public:
    int getDepth(TreeNode* s, int d){
        if(!s) return 0;
        int depth = 1 + max(getDepth(s->left, d), getDepth(s->right, d));
        if(depth == d) {
            vd.push_back(s);
        }
        return depth;
    }
    bool isIdentical(TreeNode*s, TreeNode* t) {
        if(!s && !t) return true;
        if(!s || !t || s->val != t->val) return false;
        return isIdentical(s->left, t->left) && isIdentical(s->right, t->right);
    }
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if(!t) return true;
        if(!s) return false;
        getDepth(s, getDepth(t, -1));
        for(TreeNode* n: vd){
            if(isIdentical(n, t)) return true;
        }
        return false;
    }

};
Solution 2. Convert tree to string and compare
    void traversal(TreeNode* node, vector<string>& s) {
        if(!node) {
            s.push_back("#"); return;
        }
        s.push_back(to_string(node->val));
        traversal(node->left, s);
        traversal(node->right, s);
    }
    bool isSub(vector<string>& s, vector<string>& t) {
        if(s.size()<t.size()) return false;
        for(int i=0; i<s.size();i++){
            if(s[i]!=t[0]) continue;
            for(int ii=i, j=0; ii<s.size() && j<t.size(); ii++, j++) {
                if(s[ii]!=t[j]) break;
                if(j==t.size()-1) return true;
            }
        }
        return false;
    }
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if(!t) return true;
        if(!s) return false;
        vector<string> ss, ts;
        traversal(s, ss);
        traversal(t, ts);
        return isSub(ss, ts);
    }