几种类型的二叉树

1、搜索二叉树

概念

每棵子树都是其左子树的所有值都小于根节点，右子树的所有值都大于根节点

如何判断是否为搜索二叉树

• 利用中序遍历，左 中 右（一直为升序）
• 树形dp（树形动态规划）：需要子树提供三个值，是否为BST，最小值min，最大值max

中序遍历

实现代码

递归实现：

class Node{
    int val;
    Node left;
    Node right;
}

//设置一个全局值记录遍历节点的值
public static int preValue = Integer.MIN_VALUE;
public static boolean isBST(Node head){
    //递归出口，遍历完都没有返回false，说明都满足条件，返回true
    if(head == null){
        return true;
    }
    //记录左边递归完是否满足条件
    boolean isLeftBST = isBST(head.left);
    if(!isLeftBST){
        return false;
    }
    //判断当前节点的值是否比前一个大
    if(head.val > preValue){
        //满足条件则记录当前节点值
        preValue = head.val;
    }else{
        //不满足就直接返回false
        return false;
    }
    //最后返回右边递归的结果
    return isBST(head.right);
}

栈实现：

public static void isBST2(Node head){
    if(head != null){
        //准备一个最小值，记录当前弹出节点的值
        int preValue = Integer.MIN_VALUE;
        Stack<Node> stack = new Stack<Node>();
        while(!stack.isEmpty() || head != null){
            if(head != null){
                //如果当前节点不为空，则压入栈
                stack.push(head);
                //同时前往其左节点
                head = head.left;
            }else{
                //如果当前节点为空，弹出一个节点作为当前节点
                head = stack.pop();
                //如果当前节点大于preValue，则记录，否则返回false
                if(head.val > preValue){
                    preValue = head.val;
                }else{
                    return false;
                }
                //然后前往其右节点
                head = head.right;
            }
        }
    }
    return true;
}

树形dp

实现代码

public static boolean isBST(Node head){
    
}
class ReturnData{
    boolean isBST;
    int min;
    int max;
    public ReturnData(boolean isBST,int min,int max){
        this.isBST = isBST;
        this.min = min;
        this.max = max;
    }
}
public static ReturnData process(Node x){
    //如果当前节点为空，无法得知最小值和最大值，直接返回null，让后面的判断
    if(x == null){
        return null;
    }
    //接收左子树遍历的结果
    ReturnData leftData = process(x.left);
    //接收右子树遍历的结果
    ReturnData leftData = process(x.right);
    //处理最小值和最大值
    int min = x.val;
    int max = x.val;
    //如果左子树不为空，记录此子树的最小值和最大值（与左子树的最大最小比较）
    if(leftData != null){
        min = Math.min(min,leftData.min);
        max = Math.max(max,leftData.max);
    }
    //如果右子树不为空，记录此子树的最小值和最大值（与右子树的最大最小比较）
    if(rightData != null){
        min = Math.min(min,rightData.min);
        max = Math.max(max,rightData.max);
    }
    boolean isBST = true;
    //如果此子树不满足下列条件，则不是BST，将isBST设为false
    if(leftData != null && (!leftData.isBST || leftData.max >= x.val)){
        isBST = false;
    }
    if(rightData != null && (!rightData.isBST || rightData.min <= x.val)){
        isBST = false;
    }
    //返回此子树的信息
    return new ReturnData(isBST,min,max);
}

2、完全二叉树

概念

除最后一层外，其他层节点数必须满，最后一层如果不满，则需从左往右依次变满

如何判断是否为完全二叉树

利用宽度优先遍历树：

1. 任何节点，如果有右节点没有左节点，则不是完全二叉树
2. 在不违反条件1的情况下，如果遇到了第一个左右节点不全，则后面都应该是叶节点

实现代码

public static boolean isCBT(Node head){
    if(node == null){
        return false;
    }
    Queue<Node> queue = new LinkedList<Node>();
    Node l = null, r = null;
    boolean leaf = false;//是否遇到了第一个左右不全的节点
    queue.offer(head);
    while(!queue.isEmpty()){
        head = queue.poll();
        l = head.left;
        r = head.right;
        //在没遇到的时候，如果出现了有右无左，则返回false，如果已经遇到了第一个左右节点不全的节点，这时候当前节点必须是左右
        if((leaf && (l != null || r != null)) || (l == null && r !=null)){
            return false;
        }
        if(l != null){
            queue.offer(l);
        }
        if(r != null){
            queue.offer(r);
        }
        //如果遇到了左右不全的节点，设置为true
        if(l == null || r == null){
            leaf = true;
        }
    }
    //遍历结束，没有违反，返回true
    return true;
}

3、满二叉树

概念

——国外定义的 Full Binary Tree 是说，每个节点，要么其左右节点都没有，要么都有

这里应该指的是国外定义的 Prefect Binary Tree ，即树每层的节点都是满的。设树的深度为k，树的节点数为n，则应满足 $$n = 2^k-1$$

如何判断是否为满二叉树

• 统计树的深度k，和节点数n，如果满足上述关系则为满二叉树
• 树形dp：子树需要提供两个值，子树高度、子树节点数

树形dp实现

实现代码

public static boolean isF(Node head){
    if(head == null){
        return true;
    }
    ReturnData data = process(head);
    return data.nodes == (1 << data.height - 1);
}
class ReturnData{
    int height;
    int nodes;
    public ReturnData(int height,int nodes){
        this.height = height;
        this.nodes = nodes;
    }
}
public static void process(Node x){
    //如果当前节点为空，都返回0
    if(x == null){
        return new ReturnData(0,0);
    }
    //接收遍历左子树返回的结果
    ReturnData leftData = process(x.left);
    //接收遍历右子树返回的结果
    ReturnData rightData = process(x.right);
    //记录当前子树的高度和节点数
    int height = Math.max(leftData.height,rightData.height)+1;
    int nodes = leftData.nodes + rightData.nodes + 1;
    //返回当前子树的信息
    return new ReturnData(height,nodes);
}

4、平衡二叉树（AVL树）

概念

对于任何一个子树，其左树的高度与右树的高度，差值小于等于1

如何判断是否为平衡二叉树

• 树形dp：子树需要提供两个值，是否平衡、树的高度

实现代码

public static boolean isBalanced(Node head){
    return process(head).isBalanced;
}
class ReturnData{
    public boolean isBalanced;
    public int height;
    public ReturnData(boolean isBalanced, int height){
        this.isBalanced = isBalanced;
        this.height = height;
    }
}
public static ReturnData process(Node x){
    //如果该节点为空，返回
    if(x == null){
        return new ReturnData(true,0);
    }
    //接收左树的遍历结果
    ReturnData leftData = process(x.left);
    //接收右树的遍历结果
    ReturnData rightData = process(x.right);
    //找到左右树高度较大的那个然后加1，作为当前节点所在子树的高度
    int height = Math.max(leftData.height,rightData.height);
    //记录当前节点所在子树是否平衡（其左右子树都平衡，且高度差不大于1）
    boolean isBalanced = leftData.isBalanced && rightData.isBalanced
        && Math.abs(leftData.height - right.height) <= 1;
    //返回当前子树的信息
    return new ReturnData(isBalanced,height);
}