二叉樹(shù)
二叉樹(shù)(BinaryTree)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集，它或者是空集(n=0)，或者由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的、分別稱作這個(gè)根的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。
這個(gè)定義是遞歸的。由于左、右子樹(shù)也是二叉樹(shù)， 因此子樹(shù)也可為空樹(shù)。

• 左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值
• 右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值
• 遞歸的，左右子樹(shù)也分別為二叉查找樹(shù)

紅黑樹(shù)
紅黑樹(shù)是一種含有紅黑結(jié)點(diǎn)并能自平衡的二叉查找樹(shù)。它必須滿足下面性質(zhì)：
性質(zhì)1：每個(gè)節(jié)點(diǎn)要么是黑色，要么是紅色。
性質(zhì)2：根節(jié)點(diǎn)是黑色。
性質(zhì)3：每個(gè)葉子節(jié)點(diǎn)（NIL）是黑色。
性質(zhì)4：每個(gè)紅色結(jié)點(diǎn)的兩個(gè)子結(jié)點(diǎn)一定都是黑色。
性質(zhì)5：任意一結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)的路徑都包含數(shù)量相同的黑結(jié)點(diǎn)。

一、二叉樹(shù)實(shí)現(xiàn)

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

二、二叉樹(shù)遍歷

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

非遞歸，棧實(shí)現(xiàn)

//遞歸遍歷
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)  
}

層序遍歷（廣度優(yōu)先）

借助隊(duì)列完成，先將根節(jié)點(diǎn)放入隊(duì)列中，然后出隊(duì)，接著將其左右子樹(shù)裝入隊(duì)列中。每次將根節(jié)點(diǎn)出隊(duì)后，都將其左右節(jié)點(diǎn)入隊(duì)，依次循環(huán)

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.驗(yàn)證二叉搜索樹(shù)

（1）中序遍歷后得到的集合元素為升序，即是二叉搜索樹(shù)。時(shí)間復(fù)雜度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）遞歸，遞歸左子樹(shù)，找到最大元素。遞歸右子樹(shù)，找到最小元素。判斷最大元素是否比根節(jié)點(diǎn)小，最小元素是否比根節(jié)點(diǎn)大。
時(shí)間復(fù)雜度O(N)

2.二叉樹(shù)的最近公共祖先

給定一個(gè)二叉樹(shù), 找到該樹(shù)中兩個(gè)指定節(jié)點(diǎn)的最近公共祖先。
百度百科中最近公共祖先的定義為：“對(duì)于有根樹(shù) T 的兩個(gè)結(jié)點(diǎn) p、q，最近公共祖先表示為一個(gè)結(jié)點(diǎn) x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個(gè)節(jié)點(diǎn)也可以是它自己的祖先）?！?br> 分析：首先如果p或q是根節(jié)點(diǎn)，那最近公共祖先就是根。其次如果p和q分別在左子樹(shù)和右子樹(shù)中，那最近公共祖先就是根節(jié)點(diǎn)。如果p和q在同一個(gè)棵子樹(shù)中，那么當(dāng)遞歸遍歷時(shí)，遍歷到p或q時(shí)的根節(jié)點(diǎn)就是最近公共祖先（此時(shí)的根隨著遍歷已經(jīng)發(fā)生變化，不再是原來(lái)的根）

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.二叉搜索樹(shù)的最近公共祖先

分析：根據(jù)二叉搜索樹(shù)特性，判斷p、q的值和根節(jié)點(diǎn)進(jìn)行比較。如果p和q都小于根，遍歷左子樹(shù)即可。如果p和q都大于根，遍歷右子樹(shù)即可。反之，即最近公共祖先為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;
    }
}