题目一
实现二叉树的先序，中序，后序遍历及按层遍历
递归实现先序，中序，后序遍历二叉树：
/**
* 递归遍历二叉树
*/
public class TraversalTree1 {
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int value){
this.value = value;
}
}
// 先序遍历
public static void preOrderRecursion(Node head){
if(head == null)
return;
System.out.print(head.value + " ");
preOrderRecursion(head.left);
preOrderRecursion(head.right);
}
// 中序遍历
public static void inOrderRecursion(Node head){
if(head == null)
return;
inOrderRecursion(head.left);
System.out.print(head.value + " ");
inOrderRecursion(head.right);
}
// 后序遍历
public static void posOrderRecursion(Node head){
if(head == null)
return;
posOrderRecursion(head.left);
posOrderRecursion(head.right);
System.out.print(head.value + " ");
}
}
非递归实现先序，中序，后序遍历二叉树:
import java.util.Stack;
/**
* 非递归遍历二叉树
*/
public class TraversalTree2 {
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int value){
this.value = value;
}
}
// 先序遍历
public static void preOrder(Node head){
if(head != null){
Stack<Node> stack = new Stack<>();
stack.push(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);
}
}
}
// 中序遍历
public static void inOrder(Node head){
if(head != null){
Stack<Node> stack = new Stack<>();
while(head != null || !stack.isEmpty()){
if(head != null){
stack.push(head);
head = head.left;
}else{
head = stack.pop();
System.out.print(head.value + " ");
head = head.right;
}
}
}
}
// 后序遍历
public static void porOrder(Node head){
if(head != null){
Stack<Node> stack1 = new Stack<>();
Stack<Node> stack2 = new Stack<>();
stack1.push(head);
while(!stack1.isEmpty()){
head = stack1.pop();
stack2.push(head);
if(head.left != null)
stack1.push(head.left);
if(head.right != null)
stack1.push(head.right);
}
while(!stack2.isEmpty()){
System.out.print(stack2.pop().value + " ");
}
}
}
}
按层遍历二叉树：
import java.util.LinkedList;
import java.util.Queue;
/**
* 按层遍历二叉树
*/
public class TraversalTree3 {
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int value){
this.value = value;
}
}
public static void levelOrder(Node head){
if(head != null){
Queue<Node> queue = new LinkedList<>();
queue.offer(head);
while(!queue.isEmpty()){
head = queue.poll();
System.out.print(head.value + " ");
if(head.left != null)
queue.offer(head.left);
if(head.right != null)
queue.offer(head.right);
}
}
}
}
题目二
在二叉树中找到一个节点的后继节点和前驱节点
现有一种新的二叉树节点类型如下：
public class Node{
public int value;
public Node left;
public Node right;
public Node parent;
public Node(int value){
this.value = value;
}
}
该结构比普通二叉树多了一个指向父节点的parent指针；
头节点的parent指向null;
只给一个在二叉树的某个节点node,实现返回前驱与后继节点的函数；
二叉树中序遍历的序列中，node的下一个节点叫后继，node的前一个节点叫前驱
解题思路：
如果按照中序遍历的方式去遍历整棵二叉树来寻找前驱和后继那么代价就很大，那么如何快速地找到一个节点的前驱和后继呢，思路如图：
image.png
该二叉树按照中序遍历的序列为：
4 2 5 1 6 3 7对于二叉树任意一个节点而言，都有如下结论：
如果一个节点有右子树，那么这个节点的后继节点为右子树上最左的那个节点
例如：二叉树的头节点 1 有右子树，那么后继节点为右子树上最左的那个节点即 6
反之，如果一个节点有左子树，那么这个节点的前驱节点为左子树上最右的那个节点
例如：二叉树的头节点1 有左子树，那么前驱节点为左子树上最右的那个节点 即 5如果一个节点没有右子树，那么这个节点的后继节点为以此节点为左子树的最近的根节点
例如：5这个节点没有右子树，那么这个节点的后继节点为 1；7这个节点没有右子树，那么这个节点的后继节点为null
反之，如果一个节点没有左子树，那么这个节点的前驱节点为以此节点为右子树的最近的根节点
例如：4这个节点没有左子树，那么这个节点的前驱节点为 6；5这个节点没有左子树，5的前驱为 2
实现代码如下：
public class FindSuccessorAndPrecursor {
public static class Node{
public int value;
public Node left;
public Node right;
public Node parent;
public Node(int value){
this.value = value;
}
}
// 返回一个节点的后继节点
public static Node findSuccessorNode(Node node){
if(node == null){
return null;
}
if(node.right != null){
node = node.right;
while(node.left != null){
node = node.left;
}
return node;
}else{
while(node.parent != null && node.parent.left != node){
node = node.parent;
}
return node.parent;
}
}
// 返回一个节点的前驱节点
public static Node findPrecursorNode(Node node){
if(node == null){
return null;
}
if(node.left != null){
node = node.left;
while(node.right != null){
node = node.right;
}
return node;
}else{
while(node.parent != null && node.parent.right != node){
node = node.parent;
}
return node.parent;
}
}
}
题目三
二叉树的序列化与反序列化
如有二叉树如下
1
/ \
2 3
/ \ / \
4 5 6 7
分别按照前序遍历和层遍历的方式对二叉树进行序列化和反序列化
要求：
null 用 “#”代替，每个节点直间使用“_”进行分割
前序遍历序列化的结果为：
"1_2_4_#_#_5_#_#_3_6_#_#_7_#_#_"
层序遍历学序列化的结果为：
"1_2_3_4_5_6_7_#_#_#_#_#_#_#_#_"
代码如下：
import java.util.LinkedList;
import java.util.Queue;
/**
* 二叉树的序列化与反序列化
*/
public class SerializeTree {
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int value){
this.value = value;
}
}
// 按照前序遍历的方式对二叉树序列化
public static String serializeTreeByPreOrder(Node head){
if(head == null){
return "#_";
}
String res = head.value + "_";
res += serializeTreeByPreOrder(head.left);
res += serializeTreeByPreOrder(head.right);
return res;
}
// 前序遍历反序列化
public static Node deserializeTreeByPreOrder(String str){
String[] strArr = str.split("_");
Queue<String> queue = new LinkedList<>();
for(int i = 0;i < strArr.length;i++){
queue.offer(strArr[i]);
}
return deserializeTreeByPreOrderProcess(queue);
}
public static Node deserializeTreeByPreOrderProcess(Queue<String> queue){
String value = queue.poll();
if(value.equals("#")){
return null;
}
Node head = new Node(Integer.valueOf(value));
head.left = deserializeTreeByPreOrderProcess(queue);
head.right = deserializeTreeByPreOrderProcess(queue);
return head;
}
// 按层序列化
public static String serializeTreeByLevel(Node head){
if(head == null){
return "#_";
}
Queue<Node> queue = new LinkedList<>();
queue.offer(head);
String res = head.value + "_";
while(!queue.isEmpty()){
head = queue.poll();
if(head.left != null){
res += head.left.value + "_";
queue.offer(head.left);
}else{
res += "#_";
}
if(head.right != null){
res += head.right.value + "_";
queue.offer(head.right);
}else{
res += "#_";
}
}
return res;
}
// 按层反序列化
public static Node deserializeTreeByLevel(String str){
String[] strArr = str.split("_");
int index = 0;
Node head = generateNodeByString(strArr[index++]);
if(head == null){
return null;
}
Queue<Node> queue = new LinkedList<>();
queue.offer(head);
Node node = null;
while(!queue.isEmpty()){
node = queue.poll();
node.left = generateNodeByString(strArr[index++]);
node.right = generateNodeByString(strArr[index++]);
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
}
return head;
}
public static Node generateNodeByString(String value){
if(value.equals("#")){
return null;
}
return new Node(Integer.valueOf(value));
}
}
题目四：
折纸问题
请把一段纸条竖着放在桌子上
从纸条的下边向 上方对折1次，压出折痕后展开
此时折痕的方向记作"down"
如果从纸条的下边向上方连续对折 2 次，压出折痕后展开,此时有三条折痕
从上到下的顺序依次为:down down up
给定一个输入参数N,代表纸条从下到上共对着N次
请从上到下打印所有的折痕方向
例如：N = 2时，打印" down down up "
分析：
当纸条对折一次后，产生一条折痕，纸条对折两次，产生三条折痕，纸条对折三次，产生七条折痕
我们可以知道，纸条对折N次，产生折痕的个数为：2^N-1个，这样自然而然就想到了满二叉树。
对折一次后产生的折痕的方向为down,再对折一次，在原有折痕的基础上产生新的两条折痕，为：down,up。重复若干次，产生新的两条折痕都在原有折痕的上下分别为：down up
所以，对折次数与二叉树的示意图为：
image.png
而折痕从上到下依次打印则是对这个二叉树进行中序遍历的结果
代码如下：
public class PaperFolding {
public static void printFolds(int N){
if(N <= 0){
return;
}
printProcess(1,N,true);
}
public static void printProcess(int level,int N,boolean isDown){
if(level > N){
return;
}
printProcess(level+1,N,true);
System.out.print(isDown ? "down":"up");
printProcess(level+1,N,false);
}
}
题目五
判断一棵二叉树是否是平衡二叉树
什么是平衡二叉树？
平衡二叉树对任意一个节点来说，左子树与右子树的高度差不会超过1
例如：
image.png
对该树而言，这棵树的任意一个节点的左子树和右子树的高度差不大于1，所以这棵树是一棵平很二叉树。
本题需要判断一棵树是否为平衡二叉树，解题思路如下：
如果这棵树是一棵平衡二叉树，那么对任意一个节点来讲
1.左子树是一棵平衡二叉树
2.右子树是一棵平衡二叉树
3.左子树和右子树的高度差小于等于1
本题从宏观的角度去思考，应用了递归的思想，代码如下：
public class IsBalancedTree {
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int value){
this.value = value;
}
}
// 规定balancedHeight == -1时，这棵树不是平衡的
public static class BalancedHeight{
public int balancedHeight;
public BalancedHeight(int h){
this.balancedHeight = h;
}
}
public static boolean isBalancedTree(Node head){
return getBalancedHeight(head).balancedHeight == -1 ? false : true;
}
public static BalancedHeight getBalancedHeight(Node node){
if(node == null){
return new BalancedHeight(0);
}
int leftTreeHeight = getBalancedHeight(node.left).balancedHeight;
int rightTreeHeight = getBalancedHeight(node.right).balancedHeight;
if(leftTreeHeight == -1){
return new BalancedHeight(-1);
}
if(rightTreeHeight == -1){
return new BalancedHeight(-1);
}
if(Math.abs(leftTreeHeight - rightTreeHeight) > 1){
return new BalancedHeight(-1);
}
return new BalancedHeight(Math.max(leftTreeHeight,rightTreeHeight)+1);
}
}
题目六
判断一棵树是否为二分搜索树
二分搜索树指的是，对于任意一个非叶节点都有:
node.left.value < node.value < node.right.value
举例：
image.png
上图的树即为一个二分搜索树，如果对一个二分搜索树进行中序排序，那么就可以将这棵树的节点值按照从小到大升序进行排序，依照二分搜索树这样一个特性，本题的题解即可中序遍历二分搜索树，代码如下：
import java.util.Stack;
public class IsBinarySearchTree {
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int value) {
this.value = value;
}
}
public static boolean isBinarySearchTree(Node head){
if(head == null)
return true;
Stack<Node> stack = new Stack<>();
int val = Integer.MIN_VALUE;
while(head != null || !stack.isEmpty()){
if(head != null){
stack.push(head);
head = head.left;
}else{
head = stack.pop();
if(head.value < val){
return false;
}else{
val = head.value;
}
head = head.right;
}
}
return true;
}
}
题目七
判断一棵树是否为完全二叉树
完全二叉树是指所有节点，依次按照从左至右的顺序层序排列的结构的树。例如：
image.png
那么如何判断一棵树是否为完全二叉树？
按层序遍历整个二叉树
1.如果出现一个节点，具有右子树而没有左子树，那么这棵树一定不是完全二叉树
2.当一个节点有左子树，没有右子树时，它后面所有的节点都是叶节点，否则不是完全二叉树
对于情况二，我们设定一种状态，叫做leaf,当leaf这个阶段开启，那么当前遍历到的节点后面的所有节点就都应该为叶节点，这一点是不容易想到的
代码如下：
import java.util.LinkedList;
import java.util.Queue;
public class IsCompleteBinaryTree {
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int value){
this.value = value;
}
}
public static boolean isCompleteBinaryTree(Node head){
if(head == null)
return true;
// 叶节点开启阶段
boolean leafStage = false;
Queue<Node> queue = new LinkedList<>();
queue.offer(head);
while(!queue.isEmpty()){
head = queue.poll();
if(head.left == null && head.right != null){
return false;
}
if(leafStage && (head.left != null || head.right != null)){
return false;
}
if(head.left != null){
queue.offer(head.left);
}
if(head.right != null){
queue.offer(head.right);
}else{
leafStage = true;
}
}
return true;
}
}
题目八
已知一棵树为完全二叉树，求其节点的个数
要求：时间复杂度要低于O(N),N为这棵树的节点的个数
如果要求一棵树的节点的个数，我们最先想到的就是遍历，但是遍历整棵树需要O(N)的时间复杂度，本题要求时间复杂度小于O(N)
解题思路：
image.png
当一棵完全二叉树的头节点的右子树高度等于总高度-1时，头节点的左子树必为一棵满二叉树，头节点的左满二叉树的节点个数为2^(h-1) -1个
image.png
当一棵完全二叉树的头节点的右子树的高度等于总高度-2时，头节点的右子树必为一棵满二叉树，头节点的右满二叉树的节点个数为2^(h-2)-1个
完全二叉树的任意一个子树均为完全二叉树，那么，我们可以这样设计：
如果当前节点的右子树高度等于总高度-当前节点的层数，那么以这个节点为根节点的完全二叉树的节点个数为2^(h-level) -1 +1 +右子树的个数，因为右子树也为一个完全二叉树，所以可以递归求解
如果当前节点的右子树高度不等于总高度-当前节点的层数，那么以这个节点为根节点的完全二叉树的节点个数为2^(h-level-1) -1 +1 +左子树的个数，因为左子树也为一个完全二叉树，所以同样可以递归求解
代码如下：
public class GetCBTNodeNum {
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int value){
this.value = value;
}
}
public static int getCBTNodeNum(Node head){
if(head == null)
return 0;
return getNodeNum(head,1,getHeight(head));
}
public static int getNodeNum(Node node,int level,int h){
if(level == h){
return 1;
}
// getHeight(node.right) + (level+1) -1
if(getHeight(node.right) + level == h){
// 1 << (h-level) 为2^(h-level)
// 左子树的节点个数为 2^(h-level)-1再加上头节点再加上右子树的节点数
return 1 << (h-level) + getNodeNum(node.right,level+1,h);
}else{
return 1 << (h-level-1) + getNodeNum(node.left,level+1,h);
}
}
// 获取当前节点遍历到左子树最左的点的高度
public static int getHeight(Node node){
int res = 0;
while(node != null){
node = node.left;
res++;
}
return res;
}
}
本题的重点是从宏观的角度解决问题
