二叉树/DFS总结

 1 二叉搜索树（Binary Search Tree，又名排序二叉树，二叉查找树，通常简写为BST）定义如下：
 2 空树或是具有下列性质的二叉树：
 3 （1）若左子树不空，则左子树上所有节点值均小于或等于它的根节点值；
 4 （2）若右子树不空，则右子树上所有节点值均大于或等于它的根节点值；
 5 （3）左、右子树也为二叉搜索树；
 6 
 7 BST 的特性
 8 按照中序遍历（inorder traversal）打印各节点，会得到由小到大的顺序。
 9 在BST中搜索某值的平均情况下复杂度为O(logN)O(logN)，最坏情况下复杂度为O(N)O(N)，其中N为节点个数。将待寻值与节点值比较，若不相等，则通过是小于还是大于，可断定该值只可能在左子树还是右子树，继续向该子树搜索。
10 在balanced BST中查找某值的时间复杂度为O(logN)O(logN)。
11 
12 BST 的作用
13 通过中序遍历，可快速得到升序节点列表。
14 在BST中查找元素，平均情况下时间复杂度是O(logN)O(logN)；插入新节点，保持BST特性平均情况下要耗时O（logN）。（参考链接）。
15 和有序数组的对比：有序数组查找某元素可以用二分法，时间复杂度是O（logN）；但是插入新元素，维护数组有序性要耗时O（N）。

 1 平衡二叉搜索树（Balanced Binary Search Tree，又称为AVL树，有别于AVL算法）是二叉树中的一种特殊的形态。二叉树当且仅当满足如下两个条件之一，是平衡二叉树：
 2 空树
 3 左右子树高度差绝对值不超过1且左右子树都是平衡二叉树
 4 
 5 AVL树的高度为 O(logN)O(logN)
 6 当AVL树有N个节点时，高度为O(logN)O(logN)。为何？
 7 试想一棵满二叉树，每个节点左右子树高度相同，随着树高的增加，叶子容量指数暴增，故树高一定是O(logN)O(logN)。而相比于满二叉树，AVL树仅放宽一个条件，允许左右两子树高度差1，当树高足够大时，可以把1忽略。如图是高度为9的最小AVL树，若节点更少，树高绝不会超过8，也即为何AVL树高会被限制到O(logN)O(logN)，因为树不可能太稀疏。严格的数学证明复杂,略去。
 8 
 9 为何普通二叉树不是O(logN)O(logN)？这里给出最坏的单枝树，若单枝扩展，则树高为O(N)O(N)：
10 
11 AVL树有什么用？
12 最大作用是保证查找的最坏时间复杂度为O(logN)。而且较浅的树对插入和删除等操作也更快。
13 
14 AVL树的相关练习题
15 判断一棵树是否为平衡树
16 http://www.lintcode.com/problem/balanced-binary-tree/
17 提示：可以自下而上递归判断每个节点是否平衡。若平衡将当前节点高度返回，供父节点判断;否则该树一定不平衡。

• 二叉树（Binary Tree）问题的考点剖析

　　• 第一类考察形态：求值，求路径类二叉树问题
　　• 第二类考察形态：结构变化类二叉树问题
　　• 第三类考察形态：二叉查找树（Binary Search Tree）类问题
　　　　• 非递归（Iteration）版本的中序遍历（Inorder Traversal）

碰到二叉树的问题，就想想整棵树在该问题上的结果，和左右儿子在该问题上的结果之间的联系是什么。考点都是基于树的深度优先搜索

第一类：

http://www.lintcode.com/en/problem/minimum-subtree/ 　　　　Video 15:00

http://www.lintcode.com/en/problem/binary-tree-paths/ 　　　　Video 27:00

http://www.lintcode.com/problem/lowest-common-ancestor/ 　　　Video 37:00

第二类：

http://www.lintcode.com/problem/flatten-binary-tree-to-linked-list/ 　　Video 54:00

第三类：

https://www.lintcode.com/problem/kth-smallest-element-in-a-bst/ 　　Video 1:19:30

http://www.lintcode.com/problem/binary-search-tree-iterator/
　　非递归的中序遍历：自己实现一个stack

 1 Binary Search Tree Iterator
 2 该 Iterator 算法即 non-recursion 的 inorder traversal，不仅仅适用于 BST，任何 Binary Tree 都可以
 3 • stack 中保存一路走到当前节点的所有节点
 4 • stack.peek() 一直指向 iterator 指向的当前节点
 5 • hasNext() 只需要判断 stack 是否为空
 6 • next() 只需要返回 stack.peek() 的值，并将 iterator 挪到下一个点，对 stack 进行相应的变化
 7 
 8 挪到下一个点的算法如下：
 9 • 如果当前点存在右子树，那么就是右子树中“一路向西”最左边的那个点
10 • 如果当前点不存在右子树，则是走到当前点的路径中，第一个左拐的点
11 
12 相关题：
13 http://www.lintcode.com/problem/inorder-successor-in-binary-search-tree/
14 http://www.lintcode.com/problem/validate-binary-search-tree/ 不用递归
15 http://www.lintcode.com/problem/binary-tree-inorder-traversal/ 不用递归

Follow up:　　Video 1:39:00

https://www.lintcode.com/problem/closest-binary-search-tree-value/ 　　　　Video: 1:47:40

Follow up: https://www.lintcode.com/problem/closest-binary-search-tree-value-ii

Related Questions
Search Range in Binary Search Tree
• http://www.lintcode.com/problem/search-range-in-binary-search-tree/
Insert Node in a Binary Search Tree
• http://www.lintcode.com/problem/insert-node-in-a-binary-search-tree/
Remove Node in a Binary Search Tree
• http://www.lintcode.com/problem/remove-node-in-binary-search-tree/
• http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/BST-delete.html

一个狗家高频题... Leetcode 222

 1 # Definition for a binary tree node.
 2 # class TreeNode:
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 
 8 class Solution:
 9     def countSubNodes(self, root):
10         if(root==None):
11             return 0
12         hl=0
13         rl=root.left
14         hr=0
15         rr=root.right
16         while(rl!=None):
17             hl+=1
18             rl=rl.left
19         while(rr!=None):
20             hr+=1
21             rr=rr.right
22         if(hl==hr):
23             return int(math.pow(2,hl+1))-1
24         else:
25             return self.countSubNodes(root.left) + self.countSubNodes(root.right) + 1
26         
27     def countNodes(self, root):
28         """
29         :type root: TreeNode
30         :rtype: int
31         """
32         return self.countSubNodes(root)
33     
34

View Code