001樹(shù)的相關(guān)術(shù)語(yǔ)。

樹(shù)：樹(shù)是由根節(jié)點(diǎn)和若干顆子樹(shù)構(gòu)成的。樹(shù)是由一個(gè)集合以及在該集合上定義的一種關(guān)系構(gòu)成的。集合中的元素稱為樹(shù)的節(jié)點(diǎn)，所定義的關(guān)系稱為父子關(guān)系。
二叉樹(shù)：樹(shù)是由根節(jié)點(diǎn)和若干子樹(shù)構(gòu)成的。每個(gè)節(jié)點(diǎn)最多含有兩個(gè)子樹(shù)的樹(shù)稱為二叉樹(shù)。
度：一個(gè)結(jié)點(diǎn)含有的子樹(shù)的個(gè)數(shù)
葉子節(jié)點(diǎn)或終端節(jié)點(diǎn)：度為0的節(jié)點(diǎn)
節(jié)點(diǎn)的層數(shù)： 樹(shù)根到節(jié)點(diǎn)的路徑長(zhǎng)度是該節(jié)點(diǎn)的層數(shù)，節(jié)點(diǎn)都有層數(shù)，根所在的層為0
樹(shù)的高度或深度：樹(shù)的高度或深度是樹(shù)中節(jié)點(diǎn)的最大層數(shù)（最長(zhǎng)路徑的長(zhǎng)度）加1 ，空樹(shù)高度為0，只有根節(jié)點(diǎn)的樹(shù)高度為1。  

002二叉樹(shù)有哪幾種遍歷方式。

(1)先序遍歷:先訪問(wèn)根節(jié)點(diǎn)，然后訪問(wèn)左子樹(shù)，若當(dāng)前節(jié)點(diǎn)無(wú)左子樹(shù)，則訪問(wèn)當(dāng)前節(jié)點(diǎn)的右子樹(shù)；
如上圖：
1.訪問(wèn)該二叉樹(shù)的根節(jié)點(diǎn)，找到 G；
2.訪問(wèn)節(jié)點(diǎn) G 的左子樹(shù)，找到節(jié)點(diǎn) E；
3.訪問(wèn)節(jié)點(diǎn) E的左子樹(shù)，找到節(jié)點(diǎn) D；
4.由于訪問(wèn)節(jié)點(diǎn) D左子樹(shù)失敗，且也沒(méi)有右子樹(shù)，因此以節(jié)點(diǎn) D為根節(jié)點(diǎn)的子樹(shù)遍歷完成。 但節(jié)點(diǎn) E 還沒(méi)有遍歷其右子樹(shù)，因此現(xiàn)在開(kāi)始遍歷，即訪問(wèn)節(jié)點(diǎn) A；
5.由于節(jié)點(diǎn) A 無(wú)左右子樹(shù)，因此節(jié)點(diǎn) A 遍歷完成，并且由此以節(jié)點(diǎn) E 為根節(jié)點(diǎn)的子樹(shù)也遍歷完成。現(xiàn)在回到節(jié)點(diǎn) G ，并開(kāi)始遍歷該節(jié)點(diǎn)的右子樹(shù)，即訪問(wèn)節(jié)點(diǎn) C；
6.訪問(wèn)節(jié)點(diǎn) C 左子樹(shù)，找到節(jié)點(diǎn) H；
7.由于節(jié)點(diǎn) H無(wú)左右子樹(shù)，因此節(jié)點(diǎn) H 遍歷完成，回到節(jié)點(diǎn) C 并遍歷其右子樹(shù)，找到節(jié)點(diǎn) S；
8.節(jié)點(diǎn) S 無(wú)左右子樹(shù)，因此以節(jié)點(diǎn) S為根節(jié)點(diǎn)的子樹(shù)遍歷完成，同時(shí)回歸節(jié)點(diǎn) G。由于節(jié)點(diǎn) G 的左右子樹(shù)全部遍歷完成，因此整個(gè)二叉樹(shù)遍歷完成；
9.最終遍歷的結(jié)果就是：GEDACHS
(2)中序遍歷:先訪問(wèn)左子樹(shù)，然后訪問(wèn)根節(jié)點(diǎn)，最后訪問(wèn)右子樹(shù)，即左根右。所以遍歷的結(jié)果是：DEAGHCS。
(3)后序遍歷:先訪問(wèn)左孩子，然后訪問(wèn)右孩子，最后訪問(wèn)根節(jié)點(diǎn)，即左右根。所以遍歷的結(jié)果是：DAEHSCG。
(4)寬度遍歷:從根節(jié)點(diǎn)開(kāi)始依次遍歷左子節(jié)點(diǎn)和右子節(jié)點(diǎn)，直到所有子節(jié)點(diǎn)都變遍歷完為止。所以遍歷的結(jié)果是：GECDAHS。

003二叉樹(shù)的遍歷有什么規(guī)律？

1.前序遍歷的第一個(gè)遍歷節(jié)點(diǎn)必是根節(jié)點(diǎn)，而后序遍歷的最后一個(gè)遍歷節(jié)點(diǎn)必是根節(jié)點(diǎn)；
2.根據(jù)中序遍歷順序無(wú)法判斷根節(jié)點(diǎn)，但若已知根節(jié)點(diǎn)，則可根據(jù)中序遍歷順序判斷出左子樹(shù)的組成元素和右子樹(shù)的組成元素；

004二叉樹(shù)遍歷的遞歸實(shí)現(xiàn)。

算法思路：
1.首先通過(guò)先序遍歷【GEDACHS】或者后序遍歷【DAEHSCG】可以得到二叉樹(shù)的根節(jié)點(diǎn)G，通過(guò)中序遍歷【DEAGHCS】可以得到左右子樹(shù)的成員，即左子樹(shù)的成員【DEA】,右子樹(shù)的成員是【HCS】。
2.然后將左子樹(shù)【DEA】看作新的二叉樹(shù)，通過(guò)后序遍歷【DAEHSCG】可以得到新二叉樹(shù)的根節(jié)點(diǎn)為E。又通過(guò)中序遍歷【DEAGHCS】可以得到A為E的右子樹(shù)，D為E的左子樹(shù)。
3.右子樹(shù)HCS同理
依此類推，即可畫(huà)出整棵二叉樹(shù)。不難看出，畫(huà)出這棵二叉樹(shù)的順序，就是我們想要得到的先序輸出順序，因此我們只需要在畫(huà)二叉樹(shù)時(shí)，對(duì)當(dāng)前根節(jié)點(diǎn)進(jìn)行輸出，即可完成題目需要。這樣只需要設(shè)置節(jié)點(diǎn)輸出的位置就可以得到對(duì)應(yīng)的遍歷結(jié)果。

public class Node {
    public int data;
	public Node leftChild;
	public Node rightChild;

	public Node(int data) {
		this.data = data;
	}
}
public static void OrderTraveral(TreeNode node){
    if(node == null){
        return;
    }
    //遞歸前序遍歷   根-> 左-> 右
    /*
    System.out.print(node.data+" ");
    OrderTraveral(node.leftChild);
    OrderTraveral(node.rightChild);*/
    
    //遞歸中序遍歷   左-> 根-> 右
    /*
    OrderTraveral(node.leftChild);
    System.out.print(node.data+" ");
    OrderTraveral(node.rightChild);*/
    
    //遞歸后序遍歷   左-> 右->根
    /*
    OrderTraveral(node.leftChild);
    OrderTraveral(node.rightChild);
    System.out.print(node.data+" ");*/
}

005非遞歸實(shí)現(xiàn)二叉樹(shù)的先序遍歷。

先序的思路：采用棧的先進(jìn)后出思想進(jìn)行實(shí)現(xiàn)的
1.首先有一個(gè)棧s1。
2.先將頭結(jié)點(diǎn)入棧s1。
3.頭結(jié)點(diǎn)出棧，判斷當(dāng)前結(jié)點(diǎn)的右孩子是不是為空，不為空則入棧；判斷當(dāng)前結(jié)點(diǎn)的左孩子是不是為空不為空則入棧。周而復(fù)始依次迭代。

public static void preOrder(Node head) {
	System.out.print("pre-order: ");
	if (head != null) {
		Stack<Node> stack = new Stack<Node>();
		stack.add(head);
		while (!stack.isEmpty()) {
			head = stack.pop();
			System.out.print(head.value + " ");
			if (head.right != null) {
				stack.push(head.right);
			}
			if (head.left != null) {
				stack.push(head.left);
			}
		}
	}
	System.out.println();
}

006非遞歸實(shí)現(xiàn)二叉樹(shù)的中序遍歷。

中序的思路：采用棧的先進(jìn)后出思想進(jìn)行實(shí)現(xiàn)的
1.首先有一個(gè)棧s1。
2.判斷頭結(jié)點(diǎn)是不是為空，不為空則入棧s1，并獲取頭結(jié)點(diǎn)的左節(jié)點(diǎn)。如果為空則出棧頭結(jié)點(diǎn)，并獲取頭結(jié)點(diǎn)的右節(jié)點(diǎn)。周而復(fù)始依次迭代。

public static void inOrder(Node head) {
	System.out.print("in-order: ");
	if (head != null) {
		Stack<Node> stack = new Stack<Node>();
		while (!stack.isEmpty() || head != null) {
			if (head != null) {
				stack.push(head);
				head = head.left;
			} else {
				head = stack.pop();
				System.out.print(head.value + " ");
				head = head.right;
			}
		}
	}
	System.out.println();
}

007非遞歸實(shí)現(xiàn)二叉樹(shù)的后序遍歷。

后序思路：
1.首先有兩個(gè)棧s1和s2
2.先講頭結(jié)點(diǎn)入棧s1
3.棧s1的頭結(jié)點(diǎn)出棧并入棧s2,判斷當(dāng)前結(jié)點(diǎn)的左孩子是不是為空，不為空則入棧s1；判斷當(dāng)前結(jié)點(diǎn)的右孩子是不是為空不為空則入棧s1。周而復(fù)始依次迭代，這樣循環(huán)完后s2棧的入棧的順序就是頭右左；
4.將s2彈棧，周而復(fù)始依次迭代，彈出的順序?yàn)樽笥翌^；

public static void posOrder(Node head) {
	System.out.print("pos-order: ");
	if (head != null) {
		Stack<Node> s1 = new Stack<Node>();
		Stack<Node> s2 = new Stack<Node>();
		s1.push(head);
		while (!s1.isEmpty()) {
			head = s1.pop();
			s2.push(head);
			if (head.left != null) {
				s1.push(head.left);
			}
			if (head.right != null) {
				s1.push(head.right);
			}
		}
		while (!s2.isEmpty()) {
			System.out.print(s2.pop().value + " ");
		}
	}
	System.out.println();
}

008非遞歸實(shí)現(xiàn)二叉樹(shù)的寬度遍歷。

寬度遍歷思路：
1.首先有一個(gè)隊(duì)列queue1和一個(gè)levelMap
2.先講頭結(jié)點(diǎn)入隊(duì)queue1
3.隊(duì)列queue1的頭結(jié)點(diǎn)出隊(duì)并輸出當(dāng)前節(jié)點(diǎn)，判斷當(dāng)前結(jié)點(diǎn)的左孩子是不是為空，不為空則入隊(duì)queue1；判斷當(dāng)前結(jié)點(diǎn)的右孩子是不是為空不為空則入隊(duì)queue1。周而復(fù)始依次迭代；

public static void width(Node head) {
	if(head == null) {
		return 0;
	}
	Queue<Node> queue = new LinkedList<>();
	queue.add(head);
	while(!queue.isEmpty()) {
		Node cur = queue.poll();
        System.out.println(cur.value);
		if(cur.left!=null) {
			queue.add(cur.left);
		} 
        if(cur.right!=null) {
			queue.add(cur.right);
		} 
	}
}

009求二叉樹(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;
}

010什么是搜索二叉樹(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。

011判斷搜索二叉樹(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);
}

012什么是完全二叉樹(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í)稱之為完全二叉樹(shù)。 要注意的是滿二叉樹(shù)是一種特殊的完全二叉樹(shù)。

013判斷完全二叉樹(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;
}

014如何判斷一個(gè)樹(shù)是滿二叉樹(shù)？

思路：
1.封裝一個(gè)實(shí)體類，屬性分別二叉樹(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);
}

015什么是平衡二叉樹(shù)？

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

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

1.封裝一個(gè)實(shí)體類，屬性分別為是不是平衡二叉樹(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);???
}

017二叉樹(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)；

018如何在二叉算樹(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;
    }
}