Evalsry blog | 详情

二叉树题目思路

思路

先求出当前二叉树的左树和右树的相关信息
对左树和右树的信息做处理，返回当前树的信息

题目

二叉树的完全性检验

题目：给定一个二叉树的 root ，确定它是否是一个完全二叉树。在一个完全二叉树中，除了最后一个关卡外，所有关卡都是完全被填满的，并且最后一个关卡中的所有节点都是尽可能靠左的。它可以包含 1 到 2h 节点之间的最后一级 h 。

解法一：

思路：

左树是满二叉树，右树是完全二叉树，且高度相同，则是完全二叉树
右树是满二叉树，左树是完全二叉树或者满二叉树，且高度比右二叉树加1，则是完全二叉树

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

public class Info{
    public boolean isFull;
    public boolean isCBT;
    public int height;
    
    public Info(boolean full, boolean cbt, int h) {
    	isFull = full;
    	isCBT = cbt;
    	height = h;
    }
}

public boolean isCompleteTree2(TreeNode root){
    if(root == null){
        return true;
    }
    return process(root).isCBT;
}

public Info process(TreeNode x){
    if(x == null){
        return new Info(true,true,0);
    }
    Info leftInfo = process(x.left);
    Info rightInfo = process(x.right);
    int height = Math.max(leftInfo.height,rightInfo.height)+1;
    boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height = rightInfo.height;
    boolean isCBT = false;
    if(isFull){
        isCBT = true;
    } else {
        if(leftInfo.isCBT && rightInfo.isCBT){
            //1.左树是完全二叉树，右树是满树，且左树高度比右树高度+1
            if(leftInfo.isCBT && rightInfo.isFull && leftInfo.height == rightInfo.height + 1){
                isCBT = true;
            }
            //2.左树是满树，右树是满树，且左树高度比右树高度+1
            if(leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height + 1){
                isCBT = true;
            }
            //3.左树是满树，右树是完全二叉树，且左树高度和右树高度相等
            if(leftInfo.isFull && rightInfo.isCBT && leftInfo.height == rightInfo.height){
                isCBT = true;
            }
        }
    }
    return new Info(isFull,isCBT,height);
}

解法二：

思路：

做层序遍历，如果当前二叉树中节点只有一个右节点，或者只有左节点后，剩余的节点还有叶子节点，则说明是非完全二叉树
如果当前节点没有左节点，或者没有右节点，则说明当前节点后面都没有节点，设立一个参数，noNode=true
如果noNode=true，则说明后序节点只要任意一个有子节点，则说明非完全二叉树，返回false

public boolean isCompleteTree1(TreeNode root){
    if(root == null){
        return true;
    }
    
    Queue<TreeNode> queue = new LinkedList<>();
    TreeNode cur = root;
    queue.add(root);
    boolean noNode = false;
    while(!queue.isEmpty()){
        cur = queue.poll();
        if(cur.left == null && cur.right != null){
            return false;
        }
        if(noNode && (cur.left != null && cur.right != null)){
            return false;
        }
        if(cur.left != null){
            queue.add(cur.left);
        }
        if(cur.right != null){
            queue.add(cur.right);
        }
        if(cur.left == null || cur.right == null){
            noNode = true;
        }
    }
    return true;
}

public TreeNode generateRandomBST(int maxHeight,int maxValue){
    return generate(1,maxHeight,maxValue);
}

public TreeNode generate(int h,int maxHeight,int maxValue){
    if(h > maxHeight || Math.random() < 0.5){
        return null;
    }
    TreeNode node = new TreeNode((int)(Math.random()*maxValue));
    node.left = generate(h + 1,maxHeight,maxValue);
    node.right = generate(h + 1,maxHeight,maxValue);
    return node;
}

public static void main(String[] args){
    int testTimes = 1000;
    int maxH = 5;
    int maxV = 100;
    for (int i = 0; i < testTimes; i++) {
        TreeNode test = generateRandomBST(5,100);
        if(isCompleteTree1(testNode)!=isCompleteTree2(testNode)){
        	System.out.println("失败");
        }
    }
    System.out.println("成功");
}

判断是否是搜索二叉树

题目：给定一个二叉树，判断它是否是二叉查询树。

左节点及以下节点的值比它小；
右节点及以下节点的值比它大。当然，前提是子节点都存在的情况。

public class Node{
    public int value;
    public Node left;
    public Node right;
    public Node(int data) {
    	this.value = data;
    }
}

解法一：

思路：

1. 左树是搜索二叉树，右树是搜索二叉树
1. 左树的最大值小于val，右树的最小值大于val，则当前树是搜索二叉树
1. 因此，需要收集树的max，min，isBST

public class Info{
    public int max;
    public int min;
    public boolean isBST;
    
    public Info(int max,int min,boolean isBST){
        this.max = max;
        this.min = min;
        this.isBST = isBST;
    }
}

public boolean isBST2(Node head){
    if(head == null){
        return true;
    }
    
}

public Info process2(Node head){
    if(head == null){
        return new Info(Integer.MIN_VALUE,Integer.MAX_VALUE,true);
    }
    Info leftInfo = process2(head.left);
    Info rightInfo = process2(head.right);
    int max = Math.max(Math.max(leftInfo.max,rightInfo.max),head.value);
    int min = Math.min(Math.min(leftInfo.min, rightInfo.min), head.value);
    boolean isBST = true;
    if(!leftInfo.isBST || rightInfo.isBST){
        isBST = false;
    }
    if (leftInfo.max > head.value || rightInfo.min < head.value) {
        isBST = false;
    }
    return new Info(max,min,isBST);
}

解法二：

思路：

中序遍历访问每一个节点，并将该节点保存到list中，然后判断整个list是否是升序的

public boolean isBST1(Node head){
    if(head == null){
        reuturn true;
    }
    List<Node> list = new ArrayList<>();
    inOrder(head,list);
    for(int i= 0;i < list.size();i++){
        if(list.get(i) > list.get(i+1)){
            return false;
        }
    }
    return true;
}

public void inOrder(Node head,List<Integer> list){
    if(head == null){
        return;
    }
    inOrder(head.left,list);
    list.add(head);
    inOrder(head.right,list);
}

判断是否是平衡二叉树

题目：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

public class Node{
    public int value;
    public Node left;
    public Node right;
    
    public Node(int data){
        this.value = data;
    }
}

解法一：

思路：

左树的高度和右树的高度差不超过1，且左树是平衡二叉树，右树是平衡二叉树

public boolean isBalanced1(Node head){
    if(head == null){
        return true;
    }
    return process1(head).isBal;
}

public class Info{
    public int height;
    public boolean isBal;
    
    public Info(int h,boolean isBal){
        this.height = h;
        this.isBal = isBal;
    }
}

public Info process1(Node head){
    if(head == null){
        return new Info(0,true);
    }
    Info leftInfo = process(head.left);
    Info rightInfo = process(head.right);
    int height = Math.max(leftInfo.height,rightInfo.height) + 1;
    boolean isBal = true;
    if(!leftInfo.isBal || !rightInfo.isBal){
        isBal = false;
    }
    if(Math.abs(leftInfo.height - rightInfo.height) > 1){
        isBal = false;
    }
    return new Info(height,isBal);
}

解法二：

返回当前节点的左树高度和右树高度，判断左树高度和右树是否大于1，大于，isBal=false

public boolean isBalanced2(Node head){
    if(head == null){
        return true;
    }
    boolean[] isBal = new boolean[1];
    isBal[0] = true;
    process2(head,isBal);
    return isBal[0];
}

public int process2(Node head,boolean[] isBal){
    if(head == null){
        return 0;
    }
    if(isBal[0] == false){
        return 0;
    }
    int leftHeight = process2(head.left,isBal);
    int rightHeight = process2(head.right,isBal);
    int h = Math.max(leftHight,rightHeight)+1;
    if(Math.abs(leftHeight - rightHeight) > 1){
        isBal[0] = false;
    }
    return h;
}

判断是否是满二叉树

题目：一个高度为h，并且含有2^h - 1个节点的二叉树称为满二叉树，下文称呼满二叉树为FBT。

public class Node{
    public int value;
    public Node left;
    public Node right;
    
    public Node(int data){
        this.value = data;
    }
}

解法一：

思路：

左树是满二叉树，右树是满二叉树，且左树高度等于右树高度，则当前树是满二叉树

public boolean isFull2(Node head){
    if(head == null){
        return true;
    }
    return process2(head).isFull;
}

public class Info2{
    public boolean isFull;
    public int height;
    
    public Info2(boolean isFull, int height){
        this.isFull = isFull;
        this.height = height;
    }
}

public Info2 process2(Node head){
    if(head == null){
        return new Info2(true,0);
    }
    Info2 leftInfo = process2(head.left);
    Info2 rightInfo = process2(head.right);
    int h = Math.max(leftInfo.height,rightInfo.height)+1;
    boolean isFull = true;
    if(!leftInfo.isFull || !rightInfo.isFull || leftInfo.height != rightInfo.height){
        isFull = false;
    }
    return new Info2(isFull,h);
}

解法二：

思路：

满二叉树满足$n=2^h-1$这个公式，因此，只需要知道当前树的结点个数n和高度h

public boolean isFull1(Node head){
    if(head == null){
        return true;
    }
    Info1 i = process1(head);
    return 2<<i.h == i.c+1;
    // (int)(Math.pow(2,i.h) -1) == i.c;
}

public class Info1{
    public int h;
    public int c;
    public Info1(int h ,int c){
        this.h = h;
        this.c = c;
    }
}

public Info1 process1(Node head){
    if(head == null){
        return new Info(0,0);
    }
    Info1 leftInfo = process1(head.left);
    Info2 rightInfo = process1(head.right);
    int h = Math.max(leftInfo.h,rightInfo.h) + 1;
    int c = leftInfo.c + rightInfo.c + 1;
    return new Info1(h,c);
}