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;
    }
}