1. 二叉樹的深度
分析：
如果一棵樹只有一個結(jié)點，它的深度為1。否則樹的深度就是其左、右子樹深度的較大值再加1。
算法如下：
public static int treeDepth(BinaryTreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = treeDepth(root.left);
int rightDepth = treeDepth(root.right);
// +1 是加上根結(jié)點的深度1。
return 1+(leftDepth >rightDepth? leftDepth : rightDepth );
}
2. 二叉樹的下一個結(jié)點
給定一個二叉樹和其中的一個結(jié)點，請找出中序遍歷順序的下一個結(jié)點并且返回。注意，樹中的結(jié)點不僅包含左右子結(jié)點，同時包含指向父結(jié)點的指針。二叉樹定義如下：
class BinaryTreeNode {
int value;
BinaryTreeNode leftChild;
BinaryTreeNode rightChild;
BinaryTreeNode parent;
public BinaryTreeNode(int value) {
this.value = value;
}
}
根據(jù)中序遍歷（左-根-右）分析：
-
如果該結(jié)點有右子樹，那么它的下一個結(jié)點就是它的
右子樹中的最左孩子。也就是說右子結(jié)點出發(fā)一直沿著指向左子結(jié)點的指針，我們就能找到它的下一個結(jié)點。
如果該結(jié)點
沒有右子樹并且它是它父結(jié)點的左孩子，那么它的下一個結(jié)點就是它的父結(jié)點。-
如果該結(jié)點
沒有右子樹并且它是它父結(jié)點的右孩子，這種情形就比較復(fù)雜。我們可以沿著指向父節(jié)點的指針一直向上遍歷，直到找到一個是它父結(jié)點的左孩子的結(jié)點。如果這樣的結(jié)點存在，那么這個結(jié)點的父結(jié)點就是我們要找的下一個結(jié)點。
算法：
public BinaryTreeNode getNext(BinaryTreeNode node) {
if (node == null) {
return null;
}
// 保存要查找的下一個節(jié)點
BinaryTreeNode target = null;
if (node.rightChild != null) {
target = node.rightChild;
while (target.leftChild != null) {
target = target.leftChild;
}
return target;
} else if (node.parent != null) {
target = node.parent;
BinaryTreeNode current = node;
while (target != null) {
//當(dāng)父結(jié)點的左孩子是當(dāng)前結(jié)點，就返回父結(jié)點
if (target.leftChild == current) {
return target;
}
//否則一直向上父結(jié)點
current = target;
target = target.parent;
}
}
return null;//該結(jié)點本身就是中序遍歷最后一個結(jié)點
}
3. 重建二叉樹
輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如：前序遍歷序列｛ 1, 2, 4, 7, 3, 5, 6, 8｝和中序遍歷序列｛4, 7, 2, 1, 5, 3, 8，6}，重建二叉樹并輸出它的頭結(jié)點。
分析：
- 前序遍歷的第一個是根結(jié)點（紅色1）
- 遍歷Inorder找到1為止，之前的都是1的左子樹。左子樹的size為3，1往后是右子樹
- 遍歷Preorder，1往后size個數(shù)都是左子樹，左子樹往后是右子樹
-
1~3 過程完成了一個結(jié)點的賦值（key，leftChild，rightChild），把左子樹和右子樹遞歸執(zhí)行1~3 完成左子樹結(jié)點和右子樹結(jié)點的賦值。結(jié)果如下：
分析第一次遍歷時，左右子樹的位置規(guī)律：
- preStart ：前序遍歷數(shù)組的起點
- preEnd ：前序遍歷數(shù)組的終點
- inStart ：中序遍歷數(shù)組的起點
- inIndex：前序遍歷數(shù)組中得到的根結(jié)點在中序遍歷數(shù)組中的位置
- leftTreeSize ：根結(jié)點左子樹的個數(shù)
| preStart | preEnd | inStart | inIndex | leftTreeSize |
|---|---|---|---|---|
| 0 | 7 | 0 | 3（inOrder中查找出位置）
|
3=inIndex-inStart
|
計算左子樹的位置規(guī)律：
- leftChildStart：左子樹起點 在preOrder位置
- leftChildEnd ：左子樹終點 在preOrder位置
- leftChild_inStart ：左子樹起點 在InOrder位置
| leftChildStart | leftChildEnd | leftChild_inStart |
|---|---|---|
1=preStart+1
|
3=preStart+leftTreeSize
|
0= inStart
|
計算右子樹的位置規(guī)律：
- rightChildStart：右子樹起點 在preOrder位置
- rightChildEnd：右子樹終點 在preOrder位置
- rightChild_inStart：右子樹起點 在InOrder位置
| rightChildStart | rightChildEnd | rightChild_inStart |
|---|---|---|
4 =leftChildEnd+1=preStart+leftTreeSize+1
|
7=preEnd
|
4 =inIndex+1
|
上面的過程就完成了根結(jié)點的建立（根結(jié)點賦值、區(qū)分左右子樹），接下來把左右子樹看成一棵樹遞歸執(zhí)行上面過程，就完成了二叉樹的重建。
二叉樹定義如下：
class BinaryTreeNode{
int value;
BinaryTreeNode leftChild;
BinaryTreeNode rightChild;
public BinaryTreeNode(int value){
this.value=value;
}
}
算法如下：
// 緩存中序遍歷數(shù)組每個值對應(yīng)的索引。因為每次拿到前序遍歷數(shù)組中根結(jié)點的值，都要在中序中找到對應(yīng)的位置，從而劃分左右子樹
private Map<Integer, Integer> indexForInOrders = new HashMap<>();
/**
*
* @param preOrder 前序遍歷數(shù)組
* @param inOrder 中序遍歷數(shù)組
* @return
*/
public BinaryTreeNode reConstructBT(int[] preOrder,int[] inOrder){
// 輸入的合法性判斷，兩個數(shù)組都不能為空，并且都有數(shù)據(jù)，而且數(shù)據(jù)的數(shù)目相同
if (preOrder == null || inOrder == null || preOrder.length != inOrder.length || inOrder.length < 1) {
return null;
}
for (int i=0;i<inOrder.length;i++){
indexForInOrders.put(inOrder[i],i);
}
return reConstructBT(preOrder,0,preOrder.length-1,0);
}
/**
*
* @param preOrder 前序遍歷數(shù)組
* @param preStart 前序遍歷數(shù)組的起點
* @param preEnd 前序遍歷數(shù)組的終點
* @param inStart 中序遍歷數(shù)組的起點
* @return
*/
private BinaryTreeNode reConstructBT(int[] preOrder,int preStart,int preEnd,int inStart){
if (preStart<preEnd){
return null;
}
BinaryTreeNode root=new BinaryTreeNode(preOrder[preStart]);
//找到根結(jié)點在數(shù)組中位置
int inIndex=indexForInOrders.get(root.value);
//計算根結(jié)點左子樹的個數(shù)，“-inStart”是因為遞歸里面中序數(shù)組開始的地方會發(fā)生變化
int leftTreeSize=inIndex-inStart;
// 每次遞歸時，位置信息都符合以下規(guī)律
root.leftChild=reConstructBT(preOrder, preStart+1, preStart+leftTreeSize, inStart);
root.rightChild=reConstructBT(preOrder,preStart+leftTreeSize+1,preEnd,inIndex+1);
return root;
}
4. 二叉樹的鏡像
鏡像說明圖.1
image.png.2
左子樹變成右子樹，右子樹變成左子樹
二叉樹的節(jié)點定義如下：
class TreeNode {
int value;
TreeNode left;
TreeNode right;
}
4.1 遞歸實現(xiàn)
public void Mirror(TreeNode root) {
if (root == null)
return;
swap(root);
Mirror(root.left);
Mirror(root.right);
}
private void swap(TreeNode root) {
TreeNode t = root.left;
root.left = root.right;
root.right = t;
}
4.2 非遞歸實現(xiàn)
TreeNode mirror(TreeNode root) {
if (root == null || (root.left == null && root.right == null)) {
return root;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
while (node != null || stack.size() > 0) {
while (node != null) {
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
stack.push(node);
node = node.left;
}
if (stack.size() > 0) {
node = stack.pop();
node = node.right;
}
}
return node;
}
5. 對稱的二叉樹
對稱的二叉樹說明圖
左-根-右和右-根-左遍歷的數(shù)組一致，對稱的二叉樹鏡像后不變。
算法如下：
boolean isSymmetrical(TreeNode pRoot) {
if (pRoot == null)
return true;
return isSymmetrical(pRoot.left, pRoot.right);
}
// 兩棵樹比較，那么t1的左子樹要和t2的右子樹相同；t1的右子樹要和t2的左子樹相同
boolean isSymmetrical(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null)
return true;
if (t1 == null || t2 == null)
return false;
if (t1.val != t2.val)
return false;
return isSymmetrical(t1.left, t2.right) && isSymmetrical(t1.right, t2.left);
}
6. 從上往下打印二叉樹
從上往下打印出二叉樹的每個節(jié)點，同層節(jié)點從左至右打印。例如，以下二叉樹層次遍歷的結(jié)果為：1,2,3,4,5,6,7
提示：使用對列（先進(jìn)先出）
算法如下：
public void printFromTopToBottom(TreeNode root) {
if(root==null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode t = queue.poll();
System.out.println(t.value); //打印
if(t.left!=null){ queue.add(t.left); }
if(t.right!=null){ queue.add(t.right); }
}
}
7. 把二叉樹打印出多行
從上往下打印出二叉樹的每個節(jié)點，同層節(jié)點從左至右打印。每一層打印成一行。
public void printToLines(TreeNode root) {
if(root==null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
//當(dāng)前層的結(jié)點個數(shù)
int current = 1;
// 記錄下一層的結(jié)點個數(shù)
int next = 0;
while (!queue.isEmpty()) {
TreeNode t = queue.poll();
current--;
System.out.println(t.value); //打印
if(t.left!=null){ queue.add(t.left); next++; }
if(t.right!=null){ queue.add(t.right); next++; }
//current == 0 時，說明當(dāng)前行已經(jīng)打印完了
if (current == 0) {
System.out.println();
current = next;
next = 0;
}
}
}
8. 按Z字形順序打印二叉樹
請實現(xiàn)一個函數(shù)按照之字形打印二叉樹，即第一行按照從左到右的順序打印，第二層按照從右至左的順序打印，第三行按照從左到右的順序打印，其他行以此類推。
例如，以下二叉樹按之字形順序打印的結(jié)果為：1（從左到右）,3,2（從右到左）,4,5,6,7（從左到右）
分析：
- 當(dāng)打印1時，會存取它的左右孩子2、3
- 下一層的打印順序為3->2，可以看出后進(jìn)先出，所以要用到棧
- 打印3的時候會存取它的左右孩子6、7，但是下一層的打印順序是4->5->6->7,6在7前面，說明7要先放入棧內(nèi)才會后打印出來。
- 綜上說明：當(dāng)從左向右打印時要先保存左孩子再保存右孩子；當(dāng)從右向左打印時要先保存右孩子再保存左孩子
-
假設(shè)只有一個棧，那么同一層的結(jié)點還沒被打印，就會打印下一層的結(jié)點了，如圖當(dāng)取出3打印之后并不會先打印同層的2，因為3的右、左孩子被添加到棧了。說明一個棧無法實現(xiàn)算法。
-
當(dāng)有兩個棧時，就可以實現(xiàn)算法：當(dāng)打印Stack1的3時，向Stack2添加7、6；當(dāng)打印Stack1的2時，向Stack2添加5、4；當(dāng)Stack1為空時，打印Stack2的內(nèi)容，這時又可以向Stack1添加Stack2元素的孩子
算法如下：
public void zPrint(BinaryTreeNode root) {
if (root == null) {
return;
}
Stack<BinaryTreeNode> currentStack = new Stack<>();
Stack<BinaryTreeNode> reverseStack = new Stack<>();
int flag = 0;
BinaryTreeNode node;
currentStack.add(root);
while (currentStack.size() > 0) {
node = currentStack.pop();
System.out.println(node.value);
// 當(dāng)前是從左往右打印的，那就先添加左孩子，再右孩子
if (flag == 0) {
if (node.leftChild != null) {
reverseStack.add(node.leftChild);
}
if (node.rightChild != null) {
reverseStack.add(node.rightChild);
}
} else { // 當(dāng)前是從右往左打印的，那就先添加右孩子，再左孩子
if (node.rightChild != null) {
reverseStack.add(node.rightChild);
}
if (node.rightChild != null) {
reverseStack.add(node.rightChild);
}
}
if (currentStack.size() == 0) {
flag = 1 - flag;//flag取0或1
// currentStack和reverseStack互換，達(dá)到輪流打印一個棧中的全部元素
Stack<BinaryTreeNode> temp = currentStack;
currentStack = reverseStack;
reverseStack = temp;
/* 如果每一層要換行，就執(zhí)行該語句
System.out.println();*/
}
}
}
9. 二叉樹中和為某一值的路徑
輸入一棵二叉樹和一個整數(shù)， 打印出二叉樹中結(jié)點值的和為輸入整數(shù)的所有路徑。從樹的根結(jié)點開始往下一直到葉結(jié)點所經(jīng)過的結(jié)點形成一條路徑。
分析：
- 由于路徑是從根結(jié)點出發(fā)到葉結(jié)點， 也就是說路徑總是以根結(jié)點為起始點，因此我們首先需要遍歷根結(jié)點。在樹的前序、中序、后序三種遍歷方式中，只有前序遍歷是首先訪問根結(jié)點的。
- 當(dāng)用前序遍歷的方式訪問到某一結(jié)點時， 我們把
該結(jié)點添加到路徑上，并累加該結(jié)點的值。 - 如果當(dāng)前結(jié)點不是葉子結(jié)點，則繼續(xù)訪問它的子結(jié)點。
- 如果該結(jié)點為葉結(jié)點并且路徑中結(jié)點值的和剛好等于輸入的整數(shù)， 則當(dāng)前的路徑符合要求，我們把它打印出來。
- 當(dāng)前
葉子結(jié)點訪問結(jié)束之后，要在路徑上刪除當(dāng)前結(jié)點并減去當(dāng)前結(jié)點的值，以確保返回父節(jié)點后的路徑為根結(jié)點到父結(jié)點。 - 葉子后進(jìn)先出，很容易聯(lián)想到要
利用棧。但是在這個算法中，更好的方式利用List：list.add(node)和 list.remove( list.size()-1 )聯(lián)合使用可以實現(xiàn)棧的效果，list從頭開始打印就能完成打印出路徑。而如果用棧的話，因為根結(jié)點會在葉子結(jié)點的底部，所以打印路徑時沒法從上層往下層打印。
算法如下：
//路徑的集合
private ArrayList<ArrayList<Integer>> paths = new ArrayList<>();
public ArrayList<ArrayList<Integer>> findPath(BinaryTreeNode root, int expectedSum) {
if (root == null) {
return null;
}
findPath(root, expectedSum, 0, new ArrayList<Integer>());
return paths;
}
private void findPath(BinaryTreeNode node, int expectedSum, int currentSum, ArrayList<Integer> path) {
currentSum += node.value;
path.add(node.value);
//如果是葉子結(jié)點，并且路徑上結(jié)點值的和等于輸入的值，則打印出這條路徑
boolean isLeaf = (node.leftChild == null && node.rightChild == null);
if (isLeaf && currentSum == expectedSum) {
paths.add(new ArrayList<>(path));
System.out.println(path); //打印path
} else { //如果不是葉子結(jié)點，則遍歷它的子結(jié)點
if (node.leftChild != null) {
findPath(node.leftChild, expectedSum, currentSum, path);
}
if (node.rightChild != null) {
findPath(node.rightChild, expectedSum, currentSum, path);
}
}
//在返回父結(jié)點之前，在路徑上刪除當(dāng)前結(jié)點
int size = path.size();
path.remove(size - 1);
}
可能你看了這個算法，還會有一個疑問，說好的返回父結(jié)點時，要減去當(dāng)前結(jié)點的值呢？
其實那是因為：算法采用先序遍歷，訪問完左子樹返回父結(jié)點之后是要訪問右子樹，但是在我們的算法遞歸時，左右子樹傳入的是同一個currentSum，左子樹數(shù)的累加并不會影響右子樹。所以當(dāng)左子樹訪問完，不用減去當(dāng)前結(jié)點值。
