1. 二叉树的深度
分析：
如果一棵树只有一个结点，它的深度为1。否则树的深度就是其左、右子树深度的较大值再加1。
算法如下：
public static int treeDepth(BinaryTreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = treeDepth(root.left);
int rightDepth = treeDepth(root.right);
// +1 是加上根结点的深度1。
return 1+(leftDepth >rightDepth? leftDepth : rightDepth );
}
2. 二叉树的下一个结点
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。二叉树定义如下：
class BinaryTreeNode {
int value;
BinaryTreeNode leftChild;
BinaryTreeNode rightChild;
BinaryTreeNode parent;
public BinaryTreeNode(int value) {
this.value = value;
}
}
根据中序遍历（左-根-右）分析：
-
如果该结点有右子树，那么它的下一个结点就是它的
右子树中的最左孩子。也就是说右子结点出发一直沿着指向左子结点的指针，我们就能找到它的下一个结点。
如果该结点
没有右子树并且它是它父结点的左孩子，那么它的下一个结点就是它的父结点。-
如果该结点
没有右子树并且它是它父结点的右孩子，这种情形就比较复杂。我们可以沿着指向父节点的指针一直向上遍历，直到找到一个是它父结点的左孩子的结点。如果这样的结点存在，那么这个结点的父结点就是我们要找的下一个结点。
算法：
public BinaryTreeNode getNext(BinaryTreeNode node) {
if (node == null) {
return null;
}
// 保存要查找的下一个节点
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) {
//当父结点的左孩子是当前结点，就返回父结点
if (target.leftChild == current) {
return target;
}
//否则一直向上父结点
current = target;
target = target.parent;
}
}
return null;//该结点本身就是中序遍历最后一个结点
}
3. 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如：前序遍历序列｛ 1, 2, 4, 7, 3, 5, 6, 8｝和中序遍历序列｛4, 7, 2, 1, 5, 3, 8，6}，重建二叉树并输出它的头结点。
分析：
- 前序遍历的第一个是根结点（红色1）
- 遍历Inorder找到1为止，之前的都是1的左子树。左子树的size为3，1往后是右子树
- 遍历Preorder，1往后size个数都是左子树，左子树往后是右子树
-
1~3 过程完成了一个结点的赋值（key，leftChild，rightChild），把左子树和右子树递归执行1~3 完成左子树结点和右子树结点的赋值。结果如下：
分析第一次遍历时，左右子树的位置规律：
- preStart ：前序遍历数组的起点
- preEnd ：前序遍历数组的终点
- inStart ：中序遍历数组的起点
- inIndex：前序遍历数组中得到的根结点在中序遍历数组中的位置
- leftTreeSize ：根结点左子树的个数
| preStart | preEnd | inStart | inIndex | leftTreeSize |
|---|---|---|---|---|
| 0 | 7 | 0 | 3（inOrder中查找出位置）
|
3=inIndex-inStart
|
计算左子树的位置规律：
- leftChildStart：左子树起点 在preOrder位置
- leftChildEnd ：左子树终点 在preOrder位置
- leftChild_inStart ：左子树起点 在InOrder位置
| leftChildStart | leftChildEnd | leftChild_inStart |
|---|---|---|
1=preStart+1
|
3=preStart+leftTreeSize
|
0= inStart
|
计算右子树的位置规律：
- rightChildStart：右子树起点 在preOrder位置
- rightChildEnd：右子树终点 在preOrder位置
- rightChild_inStart：右子树起点 在InOrder位置
| rightChildStart | rightChildEnd | rightChild_inStart |
|---|---|---|
4 =leftChildEnd+1=preStart+leftTreeSize+1
|
7=preEnd
|
4 =inIndex+1
|
上面的过程就完成了根结点的建立（根结点赋值、区分左右子树），接下来把左右子树看成一棵树递归执行上面过程，就完成了二叉树的重建。
二叉树定义如下：
class BinaryTreeNode{
int value;
BinaryTreeNode leftChild;
BinaryTreeNode rightChild;
public BinaryTreeNode(int value){
this.value=value;
}
}
算法如下：
// 缓存中序遍历数组每个值对应的索引。因为每次拿到前序遍历数组中根结点的值，都要在中序中找到对应的位置，从而划分左右子树
private Map<Integer, Integer> indexForInOrders = new HashMap<>();
/**
*
* @param preOrder 前序遍历数组
* @param inOrder 中序遍历数组
* @return
*/
public BinaryTreeNode reConstructBT(int[] preOrder,int[] inOrder){
// 输入的合法性判断，两个数组都不能为空，并且都有数据，而且数据的数目相同
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 前序遍历数组
* @param preStart 前序遍历数组的起点
* @param preEnd 前序遍历数组的终点
* @param inStart 中序遍历数组的起点
* @return
*/
private BinaryTreeNode reConstructBT(int[] preOrder,int preStart,int preEnd,int inStart){
if (preStart<preEnd){
return null;
}
BinaryTreeNode root=new BinaryTreeNode(preOrder[preStart]);
//找到根结点在数组中位置
int inIndex=indexForInOrders.get(root.value);
//计算根结点左子树的个数，“-inStart”是因为递归里面中序数组开始的地方会发生变化
int leftTreeSize=inIndex-inStart;
// 每次递归时，位置信息都符合以下规律
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
左子树变成右子树，右子树变成左子树
二叉树的节点定义如下：
class TreeNode {
int value;
TreeNode left;
TreeNode right;
}
4.1 递归实现
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 非递归实现
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. 对称的二叉树
对称的二叉树说明图
左-根-右和右-根-左遍历的数组一致，对称的二叉树镜像后不变。
算法如下：
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. 从上往下打印二叉树
从上往下打印出二叉树的每个节点，同层节点从左至右打印。例如，以下二叉树层次遍历的结果为：1,2,3,4,5,6,7
提示：使用对列（先进先出）
算法如下：
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. 把二叉树打印出多行
从上往下打印出二叉树的每个节点，同层节点从左至右打印。每一层打印成一行。
public void printToLines(TreeNode root) {
if(root==null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
//当前层的结点个数
int current = 1;
// 记录下一层的结点个数
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 时，说明当前行已经打印完了
if (current == 0) {
System.out.println();
current = next;
next = 0;
}
}
}
8. 按Z字形顺序打印二叉树
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
例如，以下二叉树按之字形顺序打印的结果为：1（从左到右）,3,2（从右到左）,4,5,6,7（从左到右）
分析：
- 当打印1时，会存取它的左右孩子2、3
- 下一层的打印顺序为3->2，可以看出后进先出，所以要用到栈
- 打印3的时候会存取它的左右孩子6、7，但是下一层的打印顺序是4->5->6->7,6在7前面，说明7要先放入栈内才会后打印出来。
- 综上说明：当从左向右打印时要先保存左孩子再保存右孩子；当从右向左打印时要先保存右孩子再保存左孩子
-
假设只有一个栈，那么同一层的结点还没被打印，就会打印下一层的结点了，如图当取出3打印之后并不会先打印同层的2，因为3的右、左孩子被添加到栈了。说明一个栈无法实现算法。
-
当有两个栈时，就可以实现算法：当打印Stack1的3时，向Stack2添加7、6；当打印Stack1的2时，向Stack2添加5、4；当Stack1为空时，打印Stack2的内容，这时又可以向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);
// 当前是从左往右打印的，那就先添加左孩子，再右孩子
if (flag == 0) {
if (node.leftChild != null) {
reverseStack.add(node.leftChild);
}
if (node.rightChild != null) {
reverseStack.add(node.rightChild);
}
} else { // 当前是从右往左打印的，那就先添加右孩子，再左孩子
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互换，达到轮流打印一个栈中的全部元素
Stack<BinaryTreeNode> temp = currentStack;
currentStack = reverseStack;
reverseStack = temp;
/* 如果每一层要换行，就执行该语句
System.out.println();*/
}
}
}
9. 二叉树中和为某一值的路径
输入一棵二叉树和一个整数， 打印出二叉树中结点值的和为输入整数的所有路径。从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
分析：
- 由于路径是从根结点出发到叶结点， 也就是说路径总是以根结点为起始点，因此我们首先需要遍历根结点。在树的前序、中序、后序三种遍历方式中，只有前序遍历是首先访问根结点的。
- 当用前序遍历的方式访问到某一结点时， 我们把
该结点添加到路径上，并累加该结点的值。 - 如果当前结点不是叶子结点，则继续访问它的子结点。
- 如果该结点为叶结点并且路径中结点值的和刚好等于输入的整数， 则当前的路径符合要求，我们把它打印出来。
- 当前
叶子结点访问结束之后，要在路径上删除当前结点并减去当前结点的值，以确保返回父节点后的路径为根结点到父结点。 - 叶子后进先出，很容易联想到要
利用栈。但是在这个算法中，更好的方式利用List：list.add(node)和 list.remove( list.size()-1 )联合使用可以实现栈的效果，list从头开始打印就能完成打印出路径。而如果用栈的话，因为根结点会在叶子结点的底部，所以打印路径时没法从上层往下层打印。
算法如下：
//路径的集合
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);
//如果是叶子结点，并且路径上结点值的和等于输入的值，则打印出这条路径
boolean isLeaf = (node.leftChild == null && node.rightChild == null);
if (isLeaf && currentSum == expectedSum) {
paths.add(new ArrayList<>(path));
System.out.println(path); //打印path
} else { //如果不是叶子结点，则遍历它的子结点
if (node.leftChild != null) {
findPath(node.leftChild, expectedSum, currentSum, path);
}
if (node.rightChild != null) {
findPath(node.rightChild, expectedSum, currentSum, path);
}
}
//在返回父结点之前，在路径上删除当前结点
int size = path.size();
path.remove(size - 1);
}
可能你看了这个算法，还会有一个疑问，说好的返回父结点时，要减去当前结点的值呢？
其实那是因为：算法采用先序遍历，访问完左子树返回父结点之后是要访问右子树，但是在我们的算法递归时，左右子树传入的是同一个currentSum，左子树数的累加并不会影响右子树。所以当左子树访问完，不用减去当前结点值。
