算法小结 -- Tree Recursive/Iterative 解法

Concepts:
Balanced tree: for any node in tree,  math.abs(left height - right height) <= 1

Iterative 解Tree方法 
用stack来存 traverse过的nodes
 while左边 然后出loop，做右边的操作
Ex: » InOrder Traversal(先打左边再打中间最后打右边)
https://leetcode.com/problems/binary-tree-inorder-traversal/

Iterative ：
while(cur!=null||!stack.isEmpty()){
    while(cur!=null){
        stack.add(cur);
        cur = cur.left;  
    }
    cur = stack.pop();
    res.add(cur.val);
    cur = cur.right;
}

Recur:
Tree traversal complexity: 
Complexity function T(n) — for all problem where tree traversal is involved — can be defined as:
T(n) = T(k) + T(n – k – 1) + c --Where k is the number of nodes on one side of root and n-k-1 on the other side.
(for binary: T(n) = 2T(n/2) + c --get O(n) by master theorem）
O(H) -space for stack, height of the tree - max depth
  
» InOrder Traversal(先打左边再打中间最后右边)
InOrder(root.left,res);
res.add(root.val)
InOrder(root.right,res);

» PostOrder Traversal(先打左边再打右边最后中间)
InOrder(root.left,res);
InOrder(root.right,res);
res.add(root.val)

» PreOrder Traversal(先打中间再打左边最后右边) 
res.add(root.val)
InOrder(root.left,res);
InOrder(root.right,res);
 




------------------------------------------- Recursion Ex:
Recur+Iteration
» 156. Binary Tree Upside Down LinkedIn
http://rainykat.blogspot.com/2017/01/leetcodelinkedin-156-binary-tree-upside.html
» 116. Populating Next Right Pointers in Each Node 微软
http://rainykat.blogspot.com/2017/01/leetcode-116-populating-next-right.html 
» 101. Symmetric Tree LinkedIn 微软 Bloomberg
http://rainykat.blogspot.com/2017/01/leetcode-101-symmetric-treerecur-itera.html 
» 230. Kth Smallest Element in a BST(Inorder traversal) G家UberBloomberg
http://rainykat.blogspot.com/2017/02/leetcode-230-kth-smallest-element-in.html 
» 226. Invert Binary Tree
http://rainykat.blogspot.com/2017/02/leetcode-226-invert-binary-treerecur.html

DFS+BFS
» 199. Binary Tree Right Side View 亚麻
http://rainykat.blogspot.com/2017/02/leetcode-199-binary-tree-right-side.html 
» 404. Sum of Left Leaves F家
http://rainykat.blogspot.com.tr/2017/01/leetcodef-404-sum-of-left-leaves-bfs-dfs.html  
» 104.111 Maximum/Minimum Depth of Binary Tree 各大家
return 1 + Math.max(helper(root.left), helper(root.right));
http://rainykat.blogspot.com/2017/01/leetcode-104-maximum-depth-of-binary.html
» 543. Diameter of Binary Tree 
http://rainykat.blogspot.com/2017/04/leetcode-543-diameter-of-binary.html 
» 235. Lowest Common Ancestor of a BST  各大家
http://rainykat.blogspot.com/2017/01/leetcode-235-lowest-common-ancestor-of.html
» 236. Lowest Common Ancestor of a Binary Tree 各大家
http://rainykat.blogspot.com/2017/01/leetcode-236-lowest-common-ancestor-of.html

➤DFS套路 O(V+E) - graph  
Complexity reference: http://www.geeksforgeeks.org/bfs-vs-dfs-binary-tree/
Tree: Time: O(N) just recursion BST # of nodes, Space: O(h) - BST height 
DFS: visit all nodes and check all edges(In tree: no need check edges--do not need to maintain a visited set for a tree, so  only n vertices)dfs: a specific form of backtracking related to searching tree structures
Space explain: the longest path is from root to deepest node, which has h nodes

» 112.113. PathSum I+II 微软Bloomberg
http://rainykat.blogspot.com/2017/01/leetcodebloogberg-112113path-sum-i-iidfs.html 
» 437. PathSum III
http://rainykat.blogspot.com/2017/01/leetcode-437-path-sum-iii-2dfs.html 
» 257. Binary Tree Paths G家F家苹果
https://leetcode.com/problems/binary-tree-paths/  
» 124. Binary Tree Maximum Path Sum 微软百度
http://rainykat.blogspot.com/2017/03/leetcode-124-binary-tree-maximum-path.html
» 129. Sum Root to Leaf Numbers
http://rainykat.blogspot.com/2017/03/leetcode-129-sum-root-to-leaf-numbersdfs.html  

» 339.364. Nested List Weight Sum I/II(DFS) LinkedIn
Nested List loop every element,when meeting list call recursion
http://rainykat.blogspot.com.tr/2017/01/leetcodelinkedin-339364-nested-list.html
» 100. Same Tree (Recursion)Recur Bloomberg
http://rainykat.blogspot.com/2017/01/leetcodebloomberg-100-same-tree.html 
» 106. Construct Binary Tree from Inorder and Postorder Traversal 微软
build a tree.
http://rainykat.blogspot.com/2017/01/leetcode-106-construct-binary-tree-from.html
» 114. Flatten Binary Tree to Linked List 微软
http://rainykat.blogspot.com/2016/12/leetcode-flatten-binary-tree-to-linked.html 
» 450. Delete Node in a BST(dfs) Uber
http://rainykat.blogspot.com/2017/01/leetcodeuber-450-delete-node-in-bstdfs.html
» 298. Binary Tree Longest Consecutive Sequence(dfs) G家
http://rainykat.blogspot.com/2017/01/leetcodeg-298-binary-tree-longest.html
» *366. Find Leaves of Binary Tree  LinkedIn
http://rainykat.blogspot.com/2016/12/leetcodelinkedin-366-find-leaves-of.html
» 108.109. Convert Sorted Array/List to Binary Search Tree(dfs) Airbnb Zenefit
http://rainykat.blogspot.com/2017/01/leetcodeairbnb-108-convert-sorted-array.html


BST相关 O(V+E)
» 98. Validate BST(Binary search tree) F家 亚麻 Bloomberg 微软
要保证右边的node值小于左边值
http://rainykat.blogspot.com/2016/12/leetcodef-validate-binary-search-tree.html
» 285. Inorder Successor in BST F家 微软
找第一个值比p大的node
http://rainykat.blogspot.com/2016/12/leetcodef-285-inorder-successor-in-bst.html
 » 173. Binary Search Tree Iterator  F家 G家 LinkedIn
Inorder traversal，从最小的找到最大的。 (先打leftmost,再parent,再rightnode的leftmost)
http://rainykat.blogspot.com/2016/12/leetcodef-g-linkedin-173-binary-search.html
 » 508. Most Frequent Subtree Sum(DFS: Post Order)
http://rainykat.blogspot.com/2017/03/leetcode-508-most-frequent-subtree.html 

---

» 110. Balanced Binary Tree Bloomberg
Link: https://leetcode.com/problems/balanced-binary-tree/
解法1*：use a global boolean to track if false ever exist at any node
Complexity: Time O(N) Space O(lgN)

public class Solution {
    public boolean isBalance = true;
    public boolean isBalanced(TreeNode root) {
        getHeight(root);
        return isBalance;
    }
    public int getHeight(TreeNode root){
        if(root == null)return 0;
        int leftH = 1 + getHeight(root.left);
        int rightH = 1 + getHeight(root.right);
        if(Math.abs(leftH-rightH) > 1){
            isBalance = false;
        }
        return Math.max(leftH, rightH);
    }
}

解法2：- traverse each node
              - find left & right height at each node to compare
Complexity: Time O(N*lgN) Space(lgN^2)

public class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null)return true;
        if(Math.abs(getHeight(root.left) - getHeight(root.right)) > 1)
            return false;
        return isBalanced(root.left)&&isBalanced(root.right);
    }
    public int getHeight(TreeNode root){
        if(root == null) return 0;
        int leftH = getHeight(root.left)+1;
        int rightH = getHeight(root.right)+1;
        return Math.max(leftH, rightH);
    }
}

---

» 100. Same Tree Bloomberg
https://leetcode.com/problems/same-tree/

public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) return true;
        if(p == null || q == null) return false;
        if(p.val == q.val){
            return(isSameTree(p.left,q.left)&&isSameTree(p.right,q.right));
        }
        return false;
    }
}

---

DFS: Recursive
BFS: Iterative (2 linked list: 1 track current layer, 1 track next layer)

---

➤ BFS-Iterative- queue(LinkedList)  O(V+E) - graph
BFS for Tree: Time Complexity O(V) = O(N) -- # of nodes
                        Space Complexity O(V) = O(N/2) = O(w) --maximum width
                       -- worst case hold half of nodes of tree in queue 
--BFS橙色为固定BFS步骤，即level order O(N), visit each node once 每次pop 当前的node

public class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null){ return 0;}
        int sum = 0;
        Queue<TreeNode> qu = new LinkedList<TreeNode>();
        qu.add(root);
        while(!qu.isEmpty()){
            TreeNode node = qu.remove();
            if(node.left!=null){
                 if(node.left.left == null && node.left.right == null){ sum += node.left.val;}//make sure left child leaf
            }
            if(node.left!=null){ qu.add(node.left);}
            if(node.right!=null){ qu.add(node.right);}
        }
        
        return sum;
    }
   
}

--BFS: height：root最大 (depth向下变大，leaf最大)- level
» 102.107. Binary Tree Level Order Traversal II(BFS)各大家
http://rainykat.blogspot.com/2017/01/leetcode-104-maximum-depth-of-binary.html
» 513.515 BFS
 

public int maxDepth(TreeNode root) {
        if(root == null)return 0;
        Queue<TreeNode> qu = new LinkedList<TreeNode>();
        int depth = 0;
        qu.add(root);
        while(!qu.isEmpty()){
            int size = qu.size();
            depth++;
            for(int i = 0; i < size; i++){//traveling current level, no need add depth
                TreeNode curr = qu.remove();
                if(curr.left != null) qu.offer(curr.left);
                if(curr.right != null) qu.offer(curr.right);
            }
        }
        return depth;
    }

» 103. Binary Tree Zigzag Level Order Traversal
http://rainykat.blogspot.com/2017/03/leetcode-103-binary-tree-zigzag-level.html 
» 314. Binary Tree Vertical Order Traversal F家G家
 http://rainykat.blogspot.com/2016/12/leetcodefg-binary-tree-vertical-order.html