001求二叉樹(shù)的最大寬度。

思路：
1. 首先有一個(gè)隊(duì)列queue1，一個(gè)levelMap，一個(gè)遍歷層數(shù)curLevel
2. 先將頭結(jié)點(diǎn)入隊(duì)queue1，并將頭結(jié)點(diǎn)所在的層數(shù)存儲(chǔ)到levelMap，一開(kāi)始頭節(jié)點(diǎn)在第一層所以levelMap.put(head, 1);
3. 隊(duì)列queue1的頭結(jié)點(diǎn)出隊(duì)，獲取頭結(jié)點(diǎn)所在的層數(shù)curNodeLevel ，如果當(dāng)前節(jié)點(diǎn)的層數(shù)curNodeLevel 和遍歷的層數(shù)levelMap相等，則讓當(dāng)前層數(shù)的節(jié)點(diǎn)curLevelNodes自加1，否則就讓遍歷的層數(shù)curLevel自加1，并且當(dāng)前層數(shù)的節(jié)點(diǎn)curLevelNodes初始化成1，確定最大寬度；判斷當(dāng)前結(jié)點(diǎn)的左孩子是不是為空，不為空則將該左孩子節(jié)點(diǎn)所在的層數(shù)存儲(chǔ)到levelMap并入隊(duì)queue1；判斷當(dāng)前結(jié)點(diǎn)的右孩子是不是為空不為空則將該右孩子節(jié)點(diǎn)所在的層數(shù)存儲(chǔ)到levelMap入隊(duì)queue1。周而復(fù)始依次迭代；

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什么是搜索二叉樹(shù)？

搜索二叉樹(shù)是一種特殊有序的二叉樹(shù)，如果一棵樹(shù)不為空，并且如果它的根節(jié)點(diǎn)左子樹(shù)不為空，那么它左子樹(shù)上面的所有節(jié)點(diǎn)的值都小于它的根節(jié)點(diǎn)的值，如果它的右子樹(shù)不為空，那么它右子樹(shù)任意節(jié)點(diǎn)的值都大于他的根節(jié)點(diǎn)的值，它的左右子樹(shù)也是二叉搜索樹(shù)。
由此可見(jiàn)，如果對(duì)二叉搜索樹(shù)進(jìn)行中序排列（左中右），那么會(huì)得到一個(gè)從小到大的序列。

上圖中序排列（左中右）后的順序應(yīng)該是：5，6，8，9，10，15，16，17。

003判斷搜索二叉樹(shù)的具體實(shí)現(xiàn)。

具體思路：判斷一棵樹(shù)是不是搜索二叉樹(shù)直接就是看中序遍歷是不是升序，如果是升序就是搜索二叉樹(shù)。

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什么是完全二叉樹(shù)？

完全二叉樹(shù)是由滿二叉樹(shù)而引出來(lái)的。對(duì)于深度為h 的，有N個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為h的滿二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)稱(chēng)之為完全二叉樹(shù)。 要注意的是滿二叉樹(shù)是一種特殊的完全二叉樹(shù)。

005判斷完全二叉樹(shù)的具體實(shí)現(xiàn)。

算法思路：
1.首先有一個(gè)隊(duì)列queue，將頭結(jié)點(diǎn)入隊(duì)queue，
2.層序遍歷的基礎(chǔ)上，將頭結(jié)點(diǎn)出隊(duì)，獲取該節(jié)點(diǎn)的左孩子和右孩子；
 如果該節(jié)點(diǎn)的左孩子為空，右孩子不為空則返回false;
 如果該節(jié)點(diǎn)的左右孩子不全為空，并且該節(jié)點(diǎn)不是葉子節(jié)點(diǎn)則返回false;
3.如果左孩子不為空，將左孩子入隊(duì)；
4.如果右孩子不為空，將右孩子入隊(duì)；
5.如果左右孩子都為空，將該節(jié)點(diǎn)設(shè)置為葉子節(jié)點(diǎn)；
6. 【2,3,4,5】步驟周而復(fù)始依次迭代；
7.最終返回true或者false；

public static boolean isCBT(Node head) {
    if (head == null) {
        return true;
    }
    LinkedList < Node > queue = new LinkedList < > ();
    // 是否遇到過(guò)左右兩個(gè)孩子不雙全的節(jié)點(diǎn)
    boolean leaf = false;
    Node l = null;
    Node r = null;
    queue.add(head);
    while (!queue.isEmpty()) {
        head = queue.poll();
        l = head.left;
        r = head.right;
        // 如果遇到了不雙全的節(jié)點(diǎn)之后，又發(fā)現(xiàn)當(dāng)前節(jié)點(diǎn)不是葉節(jié)點(diǎn)
        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如何判斷一個(gè)樹(shù)是滿二叉樹(shù)？

思路：
1.封裝一個(gè)實(shí)體類(lèi)，屬性分別二叉樹(shù)和樹(shù)的高度。
2.因?yàn)椴鸱趾蟮淖笞訕?shù)和右子樹(shù)的情況是一樣的，都是判斷自己的節(jié)點(diǎn)個(gè)數(shù)和樹(shù)的高度。采用遞歸的方法獲取樹(shù)的節(jié)點(diǎn)個(gè)數(shù)和樹(shù)的高度
3.將統(tǒng)計(jì)出的最大深度H和節(jié)點(diǎn)個(gè)數(shù)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什么是平衡二叉樹(shù)？

1.任何一個(gè)節(jié)點(diǎn)的左子樹(shù)或者右子樹(shù)都是平衡二叉樹(shù)。
2.任何一個(gè)節(jié)點(diǎn)的左子樹(shù)高度和右子樹(shù)高度差小于等于 1。

008判斷平衡二叉樹(shù)的具體實(shí)現(xiàn)。

1.封裝一個(gè)實(shí)體類(lèi)，屬性分別為是不是平衡二叉樹(shù)和樹(shù)的高度。

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

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

2.采用遞歸的方法，因?yàn)椴鸱趾蟮淖笞訕?shù)和右子樹(shù)的情況是一樣的，都是判斷自己是不是平衡二叉樹(shù)和樹(shù)的高度，通過(guò)判斷各自是不是平衡二叉樹(shù)以及計(jì)算樹(shù)高度差是否小于等于 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二叉樹(shù)的前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)是什么？

前驅(qū)節(jié)點(diǎn)：對(duì)一棵二叉樹(shù)進(jìn)行中序遍歷，遍歷后的順序，當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)為該節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)；
后繼節(jié)點(diǎn)：對(duì)一棵二叉樹(shù)進(jìn)行中序遍歷，遍歷后的順序，當(dāng)前節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)為該節(jié)點(diǎn)的后繼節(jié)點(diǎn)；

010如何在二叉算樹(shù)中找到一節(jié)點(diǎn)的后繼節(jié)點(diǎn) ？

下面結(jié)構(gòu)比普通二叉樹(shù)節(jié)點(diǎn)結(jié)構(gòu)多了一個(gè)指向父節(jié)點(diǎn)的parent指針。 如何在二叉算樹(shù)中找到一節(jié)點(diǎn)的后繼節(jié)點(diǎn)？ 

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

思路：
1.獲取該節(jié)點(diǎn)的右子樹(shù)。
2.如果右子樹(shù)不為空,獲取該右子樹(shù)的左子樹(shù)，周而復(fù)始依次迭代，得到該右子樹(shù)的最左邊的節(jié)點(diǎn)，該節(jié)點(diǎn)就是所求的后繼節(jié)點(diǎn)。

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

3.如果右子樹(shù)不為空,獲取該節(jié)點(diǎn)的父節(jié)點(diǎn)，判斷父節(jié)點(diǎn)不為空且該節(jié)點(diǎn)是不是父節(jié)點(diǎn)的左孩子，周而復(fù)始依次迭代，如果是左孩子則該父節(jié)點(diǎn)就是所求的后繼節(jié)點(diǎn)；

public static Node getSuccessorNode(Node node) {
    if (node == null) {
        return node;
    }
    if (node.right != null) {
        return getLeftMost(node.right);
    } else { // 無(wú)右子樹(shù)
        Node parent = node.parent;
        while (parent != null && parent.left != node) { // 當(dāng)前節(jié)點(diǎn)是其父親節(jié)點(diǎn)右孩子
            node = parent;
            parent = node.parent;
        }
        return parent;
    }
}