算法学习笔记第四讲

树（二叉树、二叉搜索树）与图

树/图与链表，之间具有一定的关联：

• 为为链表每个结点设置两个“next”指针，一个左一个右，就变成了二叉树；
• 进一步放开next指针数目和方向的限制，则链表就可以看成是图

Tree示意图：

关键的术语包括：

• 根（父）节点root
• 子（树）节点child
• 兄弟（树）节点siblings
• 深度（从该节点到叶子结点边数最大值）与高度（从根节点到该节点）

二叉树与完全二叉树

Graph示意图：

简单总结：

• Linked List 就是特殊化的 Tree
• Tree 就是特殊化的 Graph

Binary Search Tree

也称二叉搜索树、有序二叉树（ordered binary tree），排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

• 任意节点，若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 任意节点，若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 任意节点的左、右子树也分别为二叉查找树
• 注意，空树属于二叉排序树

下面是一颗错误的二叉搜索树示例：

正因为左子<根<右子的有序结构，二叉搜索树检索时间复杂度从O(N)降到了O(LogN)

但需要注意的是，当恰好所有节点都只有右子树或所有节点只有左子树，则二叉搜索树退化为一条单链表。二叉搜索树有可能退化为简单的O(N)

为了避免这种情况，可以将所有节点打乱重新生成相对平衡的二叉搜索树，更常用的方式是直接采用上图中最后四种结构：红黑树、Splay树、AVL树和KD树。

实战题目

1. 验证有效二叉搜索树

   • __思路一__：二叉树的特点是左子树小于根节点小于右子树，则中序遍历该树，所有节点应该是升序或降序排列关系。时间复杂度O(N)
     • 可将遍历结果输出到数组中，再与升序结果比对数组是否相同

       def isValidBST(self, root):
           inorder = self.inorder(root)
           return inorder == list(sorted(set(inorder)))//先用set去重，再用set排序
       def inorder(self, root):
           if root is None:
               return []
           return self.inorder(root.left) + [root.val] + self.inorder(root.right)

     • 也可直接在遍历过程中判断当前节点和前序节点关系即可：

       def isValidBST(self, root):
           self.prev = None
           return self. helper( root )
       def helper(self, root):
           if root is None:
               return True
           if not self.helper(root.left):
               return False
           if self.prev and self.prev.val >= root.val :
               return False
           self.prev = root
           return self.helper(root.right)

   • __思路二__：递归思路检查min < root < max，其中root是根节点大小，min是右子树所有元素的最小值，max是左子树所有元素的最大值，根节点大小应介于两者之间。时间复杂度O(N)

     public boolean isValid(TreeNode root, Integer min, Integer max) {
         if(root == null) return true;
         if(min != null && root.val <= min) return false;
         if(max != null && root.val >= max) return false;
     
         return isValid(root.left, min, root.val) && isValid(root.right, root.val, max);
     }

2. 二叉树最近公共祖先

   • 思路一：通过给定两个元素的路径寻址，具体又分为两种：
     • 若存在父亲指针，则两个元素分别向root节点遍历，寻找最近相遇（只是 一种思路，一般用不上），时间复杂度O(N)
     • 若没有父亲指针，则从root节点向下遍历，寻找最近相交的节点时间复杂度O(N)
   • 思路二：通过递归查找

     TreeNode lowestCommonAncestor(TreeNode root，TreeNode p，TreeNode q){
         if (root == null | root == p || root == q) return root;
         TreeNode left = lowestCommonAncestor( root.left, p,q);
         TreeNode right = lowestCommonAncestor( root.right,p,q);
         return left == null ? right : right == null ? left : root;//左子树为空返回右子树，右子树为空返回左子树，左右都空则返回根节点
     }

3. 二叉搜索树最近公共祖先

   • 思路：为上一题的变形，由于二叉排序树有序，所以只需判断p、q和root的大小关系

     def lowestCommonAncestor( self, root, p,q):
         if p.val < root.val > q.val://p、q的值均小于root的值，则说明p、q均在左子树中
             return self.lowestCommonAncestor(root.left,p,q)
         if p.val > root.val < q.val://p、q的值均大于root的值，则说明p、q均在右子树中
             return self.lowestCommonAncestor(root.right,p,q)
         return root//上面两种都不是，则p.val<root.val<q.val或q.val<root.val<p.val，说明root就是最近的公共祖先

二叉树遍历

1. 前序(Pre-order)：根-左-右

示意图：

代码

def preorder( self, root):
	if root:
		self.traverse_path.append(root.val)
		self.preorder(root.left)
		self.preorder( root.right)

2. 中序(In-order)：左-根-右

示意图：

def inorder(self, root):
	if root:
		self.inorder(root.left)
		self.traverse_path.append(root.val)
		self.inorder( root.right)

3. 后序(Post-order)：左-右-根

示意图：

def postorder(self,root):
	if root:
		self.postorder(root.left)
		self.postorder(root.right)
		self.traverse_path.append(root.val)