经典二叉树算法面试题

001求二叉树的最大宽度。

思路：
1. 首先有一个队列queue1，一个levelMap，一个遍历层数curLevel
2. 先将头结点入队queue1，并将头结点所在的层数存储到levelMap，一开始头节点在第一层所以levelMap.put(head, 1);
3. 队列queue1的头结点出队，获取头结点所在的层数curNodeLevel ，如果当前节点的层数curNodeLevel 和遍历的层数levelMap相等，则让当前层数的节点curLevelNodes自加1，否则就让遍历的层数curLevel自加1，并且当前层数的节点curLevelNodes初始化成1，确定最大宽度；判断当前结点的左孩子是不是为空，不为空则将该左孩子节点所在的层数存储到levelMap并入队queue1；判断当前结点的右孩子是不是为空不为空则将该右孩子节点所在的层数存储到levelMap入队queue1。周而复始依次迭代；

public static int w(Node head) {
    if (head == null) {
        return 0;
    }
    Queue < Node > queue = new LinkedList < > ();
    queue.add(head);
    HashMap < Node, Integer > levelMap = new HashMap < > ();
    levelMap.put(head, 1);
    int curLevel = 1;
    int curLevelNodes = 0;
    int max = Integer.MIN_VALUE;
    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        int curNodeLevel = levelMap.get(cur);
        if (curNodeLevel == curLevel) {
            curLevelNodes++;
        } else {
            max = Math.max(max, curLevelNodes);
            curLevel++;
            curLevelNodes = 1;
        }
        if (cur.left != null) {
            levelMap.put(cur.left, curNodeLevel + 1);
            queue.add(cur.left);
        }
        if (cur.right != null) {
            levelMap.put(cur.right, curNodeLevel + 1);
            queue.add(cur.right);
        }
    }
    return max;
}

002什么是搜索二叉树？

搜索二叉树是一种特殊有序的二叉树，如果一棵树不为空，并且如果它的根节点左子树不为空，那么它左子树上面的所有节点的值都小于它的根节点的值，如果它的右子树不为空，那么它右子树任意节点的值都大于他的根节点的值，它的左右子树也是二叉搜索树。
由此可见，如果对二叉搜索树进行中序排列（左中右），那么会得到一个从小到大的序列。

上图中序排列（左中右）后的顺序应该是：5，6，8，9，10，15，16，17。

003判断搜索二叉树的具体实现。

具体思路：判断一棵树是不是搜索二叉树直接就是看中序遍历是不是升序，如果是升序就是搜索二叉树。

public static boolean  checkBST2(Node head) {
    List<Node> lst=new ArrayList<>();
    process(head,lst);
    //查看lst的顺序是否为升序的即可
}
public static void process(TreeNode head,ListNode lst){
    if(node == null){
        return;
    } 
    //递归中序遍历   左-> 根-> 右
    process(head.leftChild);
    lst.add(head);
    process(head.rightChild);
}

004什么是完全二叉树？

完全二叉树是由满二叉树而引出来的。对于深度为h 的，有N个结点的二叉树，当且仅当其每一个结点都与深度为h的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

005判断完全二叉树的具体实现。

算法思路：
1.首先有一个队列queue，将头结点入队queue，
2.层序遍历的基础上，将头结点出队，获取该节点的左孩子和右孩子；
 如果该节点的左孩子为空，右孩子不为空则返回false;
 如果该节点的左右孩子不全为空，并且该节点不是叶子节点则返回false;
3.如果左孩子不为空，将左孩子入队；
4.如果右孩子不为空，将右孩子入队；
5.如果左右孩子都为空，将该节点设置为叶子节点；
6. 【2,3,4,5】步骤周而复始依次迭代；
7.最终返回true或者false；

public static boolean isCBT(Node head) {
    if (head == null) {
        return true;
    }
    LinkedList < Node > queue = new LinkedList < > ();
    // 是否遇到过左右两个孩子不双全的节点
    boolean leaf = false;
    Node l = null;
    Node r = null;
    queue.add(head);
    while (!queue.isEmpty()) {
        head = queue.poll();
        l = head.left;
        r = head.right;
        // 如果遇到了不双全的节点之后，又发现当前节点不是叶节点
        if ((leaf && !(l == null && r == null)) ||(l == null && r != null)) {
            return false;
        }
        if (l != null) {
            queue.add(l);
        }
        if (r != null) {
            queue.add(r);
        }
        if (l == null || r == null) {
            leaf = true;
        }
    }
    return true;
}

006如何判断一个树是满二叉树？

思路：
1.封装一个实体类，属性分别二叉树和树的高度。
2.因为拆分后的左子树和右子树的情况是一样的，都是判断自己的节点个数和树的高度。采用递归的方法获取树的节点个数和树的高度
3.将统计出的最大深度H和节点个数N，看是否满足N=2H-1。

public static class Info {
    public int height;
    public int nodes;
    public Info(int h, int n) {
        height = h;
        nodes = n;
    }
}
//=========
public static Info full(Node x) {
    if (x == null) {
        return new Info(0, 0);
    }
    Info leftData = full(x.left);
    Info rightData = full(x.right);
    int height = Math.max(leftData.height, rightData.height) + 1;
    int nodes = leftData.nodes + rightData.nodes + 1;
    return new Info(height, nodes);
}
//===========
public static boolean isF(Node head) {
    if (head == null) {
        return true;
    }
    Info data = f(head);
    return data.nodes == (1 << data.height - 1);
}

007什么是平衡二叉树？

1.任何一个节点的左子树或者右子树都是平衡二叉树。
2.任何一个节点的左子树高度和右子树高度差小于等于 1。

008判断平衡二叉树的具体实现。

1.封装一个实体类，属性分别为是不是平衡二叉树和树的高度。

public static class ReturnType {      
    public boolean isBalanced;      
    public int height;

          
    public ReturnType(boolean isB, int hei) {         
        isBalanced = isB;         
        height = hei;      
    }
}

2.采用递归的方法，因为拆分后的左子树和右子树的情况是一样的，都是判断自己是不是平衡二叉树和树的高度，通过判断各自是不是平衡二叉树以及计算树高度差是否小于等于 1。

public static ReturnType process(Node x) {      
    if (x == null) {         
        return new ReturnType(true, 0);      
    }      
    ReturnType leftData = process(x.left);      
    ReturnType rightData = process(x.right);      
    int height = Math.max(leftData.height, rightData.height) + 1;      
    boolean isBalanced = leftData.isBalanced && rightData.isBalanced && Math.abs(leftData.height - rightData.height) < 2;      
    return new ReturnType(isBalanced, height);   
}

009二叉树的前驱节点和后继节点是什么？

前驱节点：对一棵二叉树进行中序遍历，遍历后的顺序，当前节点的前一个节点为该节点的前驱节点；
后继节点：对一棵二叉树进行中序遍历，遍历后的顺序，当前节点的后一个节点为该节点的后继节点；

010如何在二叉算树中找到一节点的后继节点 ？

下面结构比普通二叉树节点结构多了一个指向父节点的parent指针。 如何在二叉算树中找到一节点的后继节点？ 

public class Node {
    public int value;
    public Node left;
    public Node right;
    public Node parent;
    public Node(int val) {
        value = val;
    }
}

思路：
1.获取该节点的右子树。
2.如果右子树不为空,获取该右子树的左子树，周而复始依次迭代，得到该右子树的最左边的节点，该节点就是所求的后继节点。

public static Node getLeftMost(Node node) {
    if (node == null) {
        return node;
    }
    while (node.left != null) {
        node = node.left;
    }
    return node;
}

3.如果右子树不为空,获取该节点的父节点，判断父节点不为空且该节点是不是父节点的左孩子，周而复始依次迭代，如果是左孩子则该父节点就是所求的后继节点；

public static Node getSuccessorNode(Node node) {
    if (node == null) {
        return node;
    }
    if (node.right != null) {
        return getLeftMost(node.right);
    } else { // 无右子树
        Node parent = node.parent;
        while (parent != null && parent.left != node) { // 当前节点是其父亲节点右孩子
            node = parent;
            parent = node.parent;
        }
        return parent;
    }
}