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

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

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

Tree示意图： 关键的术语包括：

• 根（父）节点root
• 子（树）节点child
• 兄弟（树）节点siblings
• 层数与高度

二叉树与完全二叉树

Graph示意图： 简单总结：

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

不同语言中BinaryTree的实现方法

Binary Search Tree

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

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

一颗错误的二叉搜索树

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

时间复杂度

为了避免这种情况，可以将所有节点打乱重新生成相对平衡的二叉搜索树，更常用的方式是直接采用上图中最后四种结构：红黑树、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)