ZXAlgorithm - C3 Binary Tree & D

Think the relationships between the root and childs
DC or traverse/ use class ResultType
Binary tree traversal: pre/in/post
Use DC or traverse to solve problem
Binary search tree: inorder is non-descending sequence
Quick and Merge sort: Space vs Stable
脉络是什么？
探究时间复杂度，二叉树的遍历，二叉树的DFS包括遍历，分治，非递归遍历分治，二叉搜索树

1 Time complexity II

T(n) = 2T(n/2) + O(n) = n + nlogn
T(n) = 2T(n/2) + O(1) ~= n + 2n = O(n) binary tree are almost all O(n)

2 二叉树的遍历Traverse in Binary Tree: preorder, inorder, postorder

• DC
  Initial: List<> result
• Traverse
  Initial: List<> result; void traverse(root, result);
• Non-recursion

  • 1 Preorder:
    Initial: Stack<TN> stack; List<I> result;
    Process: while (!stack.empty()) { Tree node = stack.pop() }
    L144 Binary Tree Preorder Traversal
    https://leetcode.com/problems/binary-tree-preorder-traversal/description/
    https://leetcode.com/problems/binary-tree-preorder-traversal/discuss/45273/Very-simple-iterative-Python-solution
    http://www.lintcode.com/problem/binary-tree-preorder-traversal/
    https://www.jiuzhang.com/solution/binary-tree-preorder-traversal/

  • 2 Inorder:
    Initial: Stack<TN> stack; List<I> result; TreeNode curt = root;
    Process: while (curt != null || !stack.empty()) { while (curt != null) {}}
    L94 Binary Tree Inorder Traversal
    https://leetcode.com/problems/binary-tree-inorder-traversal/description/
    http://www.lintcode.com/en/problem/binary-tree-inorder-traversal/
    https://www.jiuzhang.com/solutions/binary-tree-inorder-traversal/
    https://leetcode.com/problems/binary-tree-inorder-traversal/discuss/31381/Python-recursive-and-iterative-solutions.

  • 3 Postorder
    L145 Binary Tree Postorder Traversal
    https://leetcode.com/problems/binary-tree-postorder-traversal/
    http://www.lintcode.com/en/problem/binary-tree-postorder-traversal/
    http://www.jiuzhang.com/solutions/binary-tree-postorder-traversal/
    https://leetcode.com/problems/binary-tree-postorder-traversal/discuss/45785/Share-my-two-Python-iterative-solutions-post-order-and-modified-preorder-then-reverse

3 DFS in Binary Tree

要点

• Traverse vs DC:
  Recursion is method vs Traverse and DC are algorithm or idea realized by recursion
  Result in parameter traverse vs Result in return value dc
  Top down vs Bottom up
  Traverse is changing parameters vs DC return the outcome, not change given parameter
• Recursion vs non-recursion
  Non-recursion is using stack to simulate recursion
  Ourselves stack is heap memory ~= memory size(like 1/64-1/4 for server, 4M-64M for client)
  Stack memory ~= process memory allocated for each program and is not enough(like 512K)

• Recursion 3 essentials SDE
  Definition: get what param return what param
  Division:
  Exit: check null or leaves

  
  
• 核心
  Think the relationship between the result of the whole problem and two children
  Use class result type

3.1 Samples

Maximum Depth of binary tree
https://leetcode.com/problems/maximum-depth-of-binary-tree/description/
http://www.lintcode.com/problem/maximum-depth-of-binary-tree/
https://www.jiuzhang.com/solutions/maximum-depth-of-binary-tree/
Process: Math.max(,) + 1
Binary tree paths
https://leetcode.com/problems/binary-tree-paths/description/
https://www.jiuzhang.com/solution/binary-tree-paths/
https://www.jiuzhang.com/solution/binary-tree-paths/#tag-highlight-lang-python
https://leetcode.com/problems/binary-tree-paths/discuss/68272/Python-solutions-(dfs%2Bstack-bfs%2Bqueue-dfs-recursively).
Test: null
Initial: List<S> paths
Process: add left path, add right path, if it is leaf, add one node，"" + root.val change it into node
Minimum Subtree
http://www.lintcode.com/en/problem/minimum-subtree/ http://www.jiuzhang.com/solutions/minimum-subtree/
用一个变量存最小的树和权重

3.2 Result Type

Balanced Binary Tree
https://leetcode.com/problems/balanced-binary-tree/
https://leetcode.com/problems/balanced-binary-tree/discuss/35708/VERY-SIMPLE-Python-solutions-(iterative-and-recursive)-both-beat-90
http://www.lintcode.com/problem/balanced-binary-tree/ http://www.jiuzhang.com/solutions/balanced-binary-tree/

class Solution(object):
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        self.is_balanced = True
        self.helper(root)
        return self.is_balanced
        
        
    def helper(self, root):
        if not self.is_balanced:
            return 0
        if not root:
            return 0
        left_height = self.helper(root.left)
        right_height = self.helper(root.right)
        if abs(left_height - right_height) > 1:
            self.is_balanced = False
        return 1+max(left_height, right_height)

我感觉我的写法也挺简洁的，最重要的是理解traverse和DC的区别，参数是存在返回值里还是存在变量里
Subtree with Maximum Average
http://www.lintcode.com/problem/subtree-with-maximum-average/ http://www.jiuzhang.com/solutions/subtree-with-maximum-average/

class Solution:
    """
    @param root: the root of binary tree
    @return: the root of the maximum average of subtree
    """
    def findSubtree2(self, root):
        # write your code here
        self.max_avg = float('-inf')
        self.max_avg_tree = None
        self.helper(root)
        return self.max_avg_tree
        
    def helper(self, root):
        if not root:
            return 0, 0

        left_weight, left_size = self.helper(root.left)
        right_weight, right_size = self.helper(root.right)
        weight = left_weight + right_weight + root.val
        size = left_size + right_size + 1
        avg = weight / size
        if avg > self.max_avg:
            self.max_avg_tree = root
            self.max_avg = avg
        
        return weight, size

Lowest Common Ancestor
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
http://www.lintcode.com/problem/lowest-common-ancestor/
http://www.jiuzhang.com/solutions/lowest-common-ancestor/
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/discuss/158060/Python-DFS-tm
with parent pointer vs no parent pointer follow up: LCA II & III

3.3 Binary Search Tree

什么是BST?
左子树比根节点小，右子树不小于根节点
中序遍历是不降序列的充分非必要条件
Validate Binary Search Tree
https://leetcode.com/problems/validate-binary-search-tree/description/
http://www.lintcode.com/problem/validate-binary-search-tree/
https://www.jiuzhang.com/solutions/?search=Validate%20Binary%20Search%20Tree
https://leetcode.com/problems/validate-binary-search-tree/discuss/32178/Clean-Python-Solution
Initial: dfs(root.left, Long.MIN_VALUE, root.val) dfs(root.right, root.val Long.MAX_VALUE)
Exit: null, out of min and max
通过存一个边界范围来控制
Search in a Binary Search Tree
https://leetcode.com/problems/search-in-a-binary-search-tree/description/
https://leetcode.com/problems/search-in-a-binary-search-tree/discuss/148890/Python-3-lines-DFS-solution-w-a-very-simple-approach
3行搞定，思考的逻辑先考虑关系，再考虑终点
Convert Binary Search Tree to Doubly Linkedlist
https://www.jiuzhang.com/solution/convert-binary-search-tree-to-doubly-linked-list/
Initial: ResultType{first, last}, ResultType result; DoublyListNode node; ResultType left, ResultType right
Process: combine and return the first and last nodes of the doubly-list
Exit: if(null) null, result
Flatten Binary Tree to Linked List
https://leetcode.com/problems/flatten-binary-tree-to-linked-list/description/
https://leetcode.com/problems/flatten-binary-tree-to-linked-list/discuss/37154/8-lines-of-python-solution-(reverse-preorder-traversal)
http://www.lintcode.com/problem/flatten-binary-tree-to-linked-list/
https://www.jiuzhang.com/solutions/flatten-binary-tree-to-linked-list/
Initial: TreeNode leftLast, rightLast: last node of the flatten linkedlist
Process: left != null to connect; Then 3 conditions to return right != null; left != null; return null;
Binary Tree Path Sum
https://www.jiuzhang.com/solution/binary-tree-path-sum/
Binary Search Tree Iterator
https://leetcode.com/problems/binary-search-tree-iterator/description/
In-order Successor in Binary Search Tree
https://www.cnblogs.com/grandyang/p/5306162.html
https://www.jiuzhang.com/solutions/inorder-successor-in-binary-search-tree/
Insert Node in a Binary Search Tree
https://leetcode.com/problems/insert-into-a-binary-search-tree/description/
Remove Node in a Binary Search Tree
https://www.cnblogs.com/billzhou0223/p/5090759.html

4 Quick sort and merge sort

Quicksort

Initial: int[] A, int left, int right, int pivot = A[(left + right) /2]
Process: while(left <= right) {if(left<= right && A[left] < pivot) left++;) same at right; if (left<= right) exchange and left++ and right--;

Merge sort: use extra temp

Compare