Binary Tree And Divide Conquer

Complete Tree:  high from 0 
at lease n = 2h - 1 and full in 2（h+1）-1 方

  h      Balanced      Unbalanced, h = (n + 1)/2 - 1
 0:      ABCDE               ABCDE
        /     \             /     \
 1:    ABCD   E             ABCD   E
      /    \               /    \
 2:  AB    CD             ABC     D
    /  \  /  \           /   \
 3: A  B  C  D          AB   C
                       /  \
 4:                   A   B

完全二叉树 (Complete Binary Tree)：

A Complete Binary Tree （CBT) is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

对于一颗二叉树，假设其深度为d（d>1）。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树；

换句话说，完全二叉树从根结点到倒数第二层满足完美二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐。

完美二叉树 (Perfect Binary Tree)：

A Perfect Binary Tree(PBT) is a tree with all leaf nodes at the same depth. All internal nodes have degree 2.

二叉树的第i层至多拥有个节点数；深度为k的二叉树至多总共有个节点数，而总计拥有节点数匹配的，称为“满二叉树”；

完满二叉树 (Full Binary Tree):

A Full Binary Tree (FBT) is a tree in which every node other than the leaves has two children.

换句话说，所有非叶子结点的度都是2。（只要你有孩子，你就必然是有两个孩子。）

DFS in Binary Tree

• • Preorder / Inorder / Postorder

  • Introduce Divide Conquer Algorithm

  • Non-recursion vs Traverse vs Divide Conquer

• BFS in Binary Tree

• Binary Searh Tree

Insert / Remove / Find / Validate

Preorder前序遍历○1245 3根左右

●Inorder中序遍历 ○42513左根右

●Postorder后序遍历○452 31左右根

Traverse vs Divide Conquer

• They are both Recursion Algorithm

• Result in parameter vs Result in return value

• Top down vs Bottom up

BST 的遍历时间复杂度就是O(n)

Find successor of p in node root:

successor = None
while root is not None and root.val != p.val:
    if root.val > p.val:
        successor = root
        root = root.left
    else:
        root = root.right

平衡平衡二叉树定义(balanced Binary Tree)

高度平衡二叉树是每一个节点的两个字数的深度差不能超过1

1.构建树

• 用前序和中序建树105

• 用后序和中序建树106

• 数组构建BST 108

• 链表构建BST 109

2.树的遍历

• 前序 144

• 中序 94

• 后序 145

• 层次 102 103 107

3.树的属性

• 求深度 104

• 是否平衡是平衡树 110

• 最小深度 111

4.BST树

• 判断BST是否合法 98

• 恢复BST 99

• BST实现迭代：173（用到某一遍历）