ZXAlgorithm - C3 Binary Tree & D

2019-09-30  本文已影响0人  左心Chris

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

3 DFS in Binary Tree

要点

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

上一篇 下一篇

猜你喜欢

热点阅读