二叉树

二叉树
二叉树(BinaryTree)是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。
这个定义是递归的。由于左、右子树也是二叉树， 因此子树也可为空树。

• 左子树上所有结点的值均小于它的根节点的值
• 右子树上所有结点的值均大于它的根结点的值
• 递归的，左右子树也分别为二叉查找树

红黑树
红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质：
性质1：每个节点要么是黑色，要么是红色。
性质2：根节点是黑色。
性质3：每个叶子节点（NIL）是黑色。
性质4：每个红色结点的两个子结点一定都是黑色。
性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

一、二叉树实现

public class TreeNode{
  public int val;
  public TreeNode left,right;
  public TreeNode(int val){
      this.val=val;
      this.left=null;
      this.right=null;
   }
}

二、二叉树遍历

先序遍历(Pre-order):根-左-右：A-B-D-E-C-F-G

非递归，栈实现

//递归遍历
public void preOrder(TreeNode node){
      if(node==null)
            return;
      System.out.println(node.val)
      preOrder(node.left);
      preOrder(node.right);
}
//非递归遍历
//利用栈得特性，先压入根，每次取出根后，先压入右孩子，然后压入左孩子
public void preOrder(){
      Stack<TreeNode>  stack=new Stack<>();
      stack.push(root);
      while(!stack.isEmpty()){
          TreeNode cur=stack.pop();
           System.out.println(cur.val);
           if(cur.right!=null){
                stack.push(cur.right);
           }
           if(cur.left!=null){
                stack.push(cur.left);
           }
    }
}

中序遍历(In-order):左-根-右：D-E-B-A-F-C-G

public void preOrder(TreeNode node){
      if(node==null)
            return;
      preOrder(node.left);
      System.out.println(node.val)
      preOrder(node.right);
}

后序遍历(Post-Inder):左-右-根：D-E-B-F-G-C-A

public void preOrder(TreeNode node){
      if(node==null)
            return;
      preOrder(node.left);
      preOrder(node.right);
      System.out.println(node.val)  
}

层序遍历（广度优先）

借助队列完成，先将根节点放入队列中，然后出队，接着将其左右子树装入队列中。每次将根节点出队后，都将其左右节点入队，依次循环

public void levelOrder(TreeNode node){
    Queue<TreeNode>  q=new LinkedList<>();
    q.add(node);
    while(!q.isEmpty()){
        Node cur=q.remove();
        if(cur.left!=null){
              q.add(cur.left);
        }
        if(cur.right!=null){
              q.add(cur.right);
        }
    }
}

三、Leetcode

1.验证二叉搜索树

（1）中序遍历后得到的集合元素为升序，即是二叉搜索树。时间复杂度O(N)

class Solution{
     public boolean isValidBST(TreeNode root){
            List<Integer> list=new LinkedList<>();
            midTraverse(root,list);
            if(list.size()==0)
                  return true;
            for(int i=1;i<list.size();i++)
                  if(list.get(i-1)>=list.get(i))
                      return false;
            return true; 
      }
      private List<Integer>  midTraverse(TreeNode root,List<Integer> list){
            if(root!=null){
                  midTraverse(root.left,list);
                  list.add(root.val);
                  midTraverse(root.right,list);
            }
            return list;
      }
}

（2）递归，递归左子树，找到最大元素。递归右子树，找到最小元素。判断最大元素是否比根节点小，最小元素是否比根节点大。
时间复杂度O(N)

2.二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
分析：首先如果p或q是根节点，那最近公共祖先就是根。其次如果p和q分别在左子树和右子树中，那最近公共祖先就是根节点。如果p和q在同一个棵子树中，那么当递归遍历时，遍历到p或q时的根节点就是最近公共祖先（此时的根随着遍历已经发生变化，不再是原来的根）

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null||q==root||p==root)
              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的值和根节点进行比较。如果p和q都小于根，遍历左子树即可。如果p和q都大于根，遍历右子树即可。反之，即最近公共祖先为root。

//递归
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(p.val<root.val&&root.val>q.val)
            return lowestCommonAncestor(root.left,p,q);
        if(p.val>root.val&&root.val<q.val)
            return lowestCommonAncestor(root.right,p,q);
        return root;
    }
}