面试算法知识梳理(12) - 二叉树算法第二部分
2017-12-21 本文已影响297人
泽毛
面试算法代码知识梳理系列
- 插入排序
- 希尔排序
- 选择排序
- 冒泡排序
- 计数排序
- 基数排序
- 归并排序
- 快速排序
- 双向扫描的快速排序
- 堆排序
- 替换字符串中的空格
- 输入一个字符串，打印出该字符串的所有排列
- 第一个只出现一次的字符
- 翻转句子
- 计算字符串之间的最短距离
- 查找字符串中的最长重复子串
- 求长度为
N的字符串的最长回文子串 - 将字符串中的
*移到前部，并且不改变非*的顺序 - 不开辟用于交换的空间，完成字符串的逆序
C++ - 最短摘要生成
- 最长公共子序列
- 二维数组的整数查找
- 旋转数组中的最小数字（旋转数组中的最大数字）
- 调整数组使奇数位于偶数之前
- 找出数组中出现次数超过一半的数字
- 找到最小的
k个数 - 连续子数组的最大和
- 连续子数组的最大和（二维）
- 求数组当中的逆序对
- 在递增排序的数组中，查找指定数字出现的个数
- 查找数组中只出现一次的两个数字
- 在递增排序的数组中，查找和为
s的两个数 - 输入一个正数
s，打印出所有和为s的连续正数序列 - 数组当中的最大最小值
- 求数组当中的最长递增子序列（求数组当中的最长递减子序列）
- 区间重合判断
- 一个整数数组，长度为
n，将其分为m份，使各份的和相等，求m的最大值
- 普通二分查找
- 查找关键字第一次出现的位置
- 查找关键字最后一次出现的位置
- 查找小于关键字的最大数字出现的位置
- 查找大于关键字的最小数字出现的位置
- 新建链表
- 反转链表（递归和非递归实现）
- 获得链表倒数第
k个结点 - 获得链表的中间结点
- 删除链表结点
- 交换链表结点
- 建立二叉查找树
- 删除二叉查找树中指定元素
- 非递归遍历二叉查找树（先序遍历、中序遍历、后序遍历）
- 递归遍历二叉树（先序遍历、中序遍历、后序遍历）
- 分层打印二叉树
- 打印二叉树的第
n层 - 统计二叉树叶结点的个数
- 统计二叉树的高度
- 获得二叉树的镜像
- 判断元素是否存在于二叉树中
- 打印二叉树中和为
s的路径 - 获得二叉树的最大距离
- 判断二叉树是否是平衡树
- 将二叉树转换成为链表
- 判断数组是否为二叉树的后序遍历
- 判断某树是否是另一棵树的子树
- 根据前序和中序序列重建二叉树
一、概述
- 获得二叉树的镜像
- 判断元素是否存在于二叉树中
- 打印二叉树中和为
s的路径 - 获得二叉树的最大距离
- 判断二叉树是否是平衡树
二、代码实现
2.1 获得二叉树的镜像
代码实现
public class Untitled {
static class Tree {
int size;
Node root;
}
static class Node {
Node parent;
Node left;
Node right;
int value;
}
static void insertNode(Tree tree, int value) {
if (tree == null) {
return;
}
Node tNode = tree.root;
//待插入结点的父结点，如果遍历完为空，说明此时是一个空树。
Node pNode = null;
//新的结点。
Node nNode = new Node();
nNode.value = value;
while (tNode != null) {
pNode = tNode;
if (tNode.value > value) {
tNode = tNode.left;
} else {
tNode = tNode.right;
}
}
nNode.parent = pNode;
if (pNode == null) {
tree.root = nNode;
} else if (pNode.value > value) {
pNode.left = nNode;
} else {
pNode.right = nNode;
}
tree.size++;
}
static Tree createBinTree(int p[], int len) {
Tree tree = new Tree();
for (int i = 0; i < len; i++) {
int value = p[i];
insertNode(tree, value);
}
return tree;
}
static void swapTree(Node node) {
if (node == null) {
return;
}
Node temp = node.left;
node.left = node.right;
node.right = temp;
swapTree(node.left);
swapTree(node.right);
}
static void printInOrder(Node node) {
if (node == null) {
return;
}
printInOrder(node.left);
//遍历完左子树后，打印根结点，最后遍历右子树。
System.out.println(node.value);
printInOrder(node.right);
}
public static void main(String[] args) {
int p[] = {3, 5, 6, 1, 2, 4, -1, -3};
Tree tree = createBinTree(p, p.length);
System.out.println("- 转换前 -");
printInOrder(tree.root);
swapTree(tree.root);
System.out.println("- 转换后 -");
printInOrder(tree.root);
}
}
运行结果
- 转换前 -
-3
-1
1
2
3
4
5
6
- 转换后 -
6
5
4
3
2
1
-1
-3
2.2 判断元素是否存在于二叉树中
代码实现
public class Untitled {
static class Tree {
int size;
Node root;
}
static class Node {
Node parent;
Node left;
Node right;
int value;
}
static void insertNode(Tree tree, int value) {
if (tree == null) {
return;
}
Node tNode = tree.root;
//待插入结点的父结点，如果遍历完为空，说明此时是一个空树。
Node pNode = null;
//新的结点。
Node nNode = new Node();
nNode.value = value;
while (tNode != null) {
pNode = tNode;
if (tNode.value > value) {
tNode = tNode.left;
} else {
tNode = tNode.right;
}
}
nNode.parent = pNode;
if (pNode == null) {
tree.root = nNode;
} else if (pNode.value > value) {
pNode.left = nNode;
} else {
pNode.right = nNode;
}
tree.size++;
}
static Tree createBinTree(int p[], int len) {
Tree tree = new Tree();
for (int i = 0; i < len; i++) {
int value = p[i];
insertNode(tree, value);
}
return tree;
}
static boolean isKInTree(Node node, int k) {
if (node == null) {
return false;
}
if (node.value == k) {
return true;
}
boolean has;
//先在左子树中寻找，如果左子树中找到了，那么就不需要在右子树中寻找了。
has = isKInTree(node.left, k);
if (!has) {
has = isKInTree(node.right, k);
}
return has;
}
public static void main(String[] args) {
int p[] = {3, 5, 6, 1, 2, 4, -1, -3};
Tree tree = createBinTree(p, p.length);
System.out.println("5 is in tree=" + isKInTree(tree.root, 5));
System.out.println("9 is in tree=" + isKInTree(tree.root, 9));
}
}
运行结果
>> 5 is in tree=true
>> 9 is in tree=false
2.3 打印二叉树中和为 s 的路径
问题描述
输入一个整数和一棵二叉树，打印出和与输入整数相等的所有路径，从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
代码实现
import java.util.LinkedList;
public class Untitled {
static class Tree {
int size;
Node root;
}
static class Node {
Node parent;
Node left;
Node right;
int value;
}
static void insertNode(Tree tree, int value) {
if (tree == null) {
return;
}
Node tNode = tree.root;
//待插入结点的父结点，如果遍历完为空，说明此时是一个空树。
Node pNode = null;
//新的结点。
Node nNode = new Node();
nNode.value = value;
while (tNode != null) {
pNode = tNode;
if (tNode.value > value) {
tNode = tNode.left;
} else {
tNode = tNode.right;
}
}
nNode.parent = pNode;
if (pNode == null) {
tree.root = nNode;
} else if (pNode.value > value) {
pNode.left = nNode;
} else {
pNode.right = nNode;
}
tree.size++;
}
static Tree createBinTree(int p[], int len) {
Tree tree = new Tree();
for (int i = 0; i < len; i++) {
int value = p[i];
insertNode(tree, value);
}
return tree;
}
static void printSum(LinkedList<Node> curPath, Node curNode, int curSum, int expectSum) {
if (curNode == null) {
return;
}
curPath.offer(curNode);
boolean isLeaf = curNode.left == null && curNode.right == null;
int sum = curSum + curNode.value;
//如果是叶结点，并且和满足要求，那么打印出所有的路径。
if (isLeaf && sum == expectSum) {
for (int i = 0; i < curPath.size(); i++) {
System.out.println(String.valueOf(curPath.get(i).value));
}
} else {
printSum(curPath, curNode.left, sum, expectSum);
printSum(curPath, curNode.right, sum, expectSum);
}
//当其左右子树都遍历完之后，将当前结点出栈。
curPath.pop();
}
public static void main(String[] args) {
int p[] = {3, 5, 6, 1, 2, 4, -1, -3};
Tree tree = createBinTree(p, p.length);
printSum(new LinkedList<Node>(), tree.root, 0, 12);
}
}
运行结果
2
5
4
2.4 获得二叉树的最大距离
问题描述
二叉树距离 指的是两个 叶结点之间边的个数，计算一个二叉树的最大距离有两种情况，最终的目的就是要获得这两种情况的值，并取其最大值作为该结点的最大距离：
- 路径经过左子树的最深结点，通过根结点，再到右子树的最深结点，在这种情况下，最大距离等于左子树的高度加上右子树的高度在加上
2。 - 路径不穿过根结点，而是左子树或右子树的最大距离路径，在这种情况下，最大距离等于这两者的最大值。
对于每个结点，定义两个额外的属性，maxDistance表示 以该结点为根结点的子树的最大距离，而maxDepth为 以该结点为根结点的子树到最深结点的距离，对于每个叶结点来说，这两个值为0，而对于每个非叶结点来说，这两个值是通过它的左右孩子结点的这两个属性计算出来的。
代码实现
public class Untitled {
static class Tree {
int size;
Node root;
}
static class Node {
Node parent;
Node left;
Node right;
int value;
int maxDistance;
int maxDepth;
}
static void insertNode(Tree tree, int value) {
if (tree == null) {
return;
}
Node tNode = tree.root;
//待插入结点的父结点，如果遍历完为空，说明此时是一个空树。
Node pNode = null;
//新的结点。
Node nNode = new Node();
nNode.value = value;
while (tNode != null) {
pNode = tNode;
if (tNode.value > value) {
tNode = tNode.left;
} else {
tNode = tNode.right;
}
}
nNode.parent = pNode;
if (pNode == null) {
tree.root = nNode;
} else if (pNode.value > value) {
pNode.left = nNode;
} else {
pNode.right = nNode;
}
tree.size++;
}
static Tree createBinTree(int p[], int len) {
Tree tree = new Tree();
for (int i = 0; i < len; i++) {
int value = p[i];
insertNode(tree, value);
}
return tree;
}
static void calculateMaxTreeDistance(Node node) {
//如果是空结点，那么不需要计算。
if (node == null) {
return;
}
if (node.left == null && node.right == null) {
return;
}
int leftDistance = 0;
int leftDepth = -1;
if (node.left != null) {
calculateMaxTreeDistance(node.left);
leftDistance = node.left.maxDistance;
leftDepth = node.left.maxDepth;
}
int rightDistance = 0;
int rightDepth = -1;
if (node.right != null) {
calculateMaxTreeDistance(node.right);
rightDistance = node.left.maxDistance;
rightDepth = node.left.maxDepth;
}
//深度为左右孩子结点的深度最大值+1
node.maxDepth = leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
//(1) 通过根结点，则选取左子树的深度+右子树深度+2
int throughRoot = leftDepth + rightDepth + 2;
//(2) 不通过根结点，则选取左右子树的距离最大值。
int notThroughRoot = leftDistance > rightDistance ? leftDistance : rightDistance;
//取以上两者的最大值，作为该结点的最大距离属性。
node.maxDistance = throughRoot > notThroughRoot ? throughRoot : notThroughRoot;
}
static void printInOrder(Node node) {
if (node == null) {
return;
}
printInOrder(node.left);
//遍历完左子树后，打印根结点，最后遍历右子树。
System.out.println("value=" + node.value + ", depth=" + node.maxDepth + ", distance=" + node.maxDistance);
printInOrder(node.right);
}
public static void main(String[] args) {
int p[] = {3, 5, 6, 1, 2, 4, -1, -3};
Tree tree = createBinTree(p, p.length);
calculateMaxTreeDistance(tree.root);
System.out.println("最大距离=" + tree.root.maxDistance);
}
}
运行结果
>> 最大距离=6
2.5 判断二叉树是否是平衡树
问题描述
平衡二叉树 具有以下性质：它是一棵空树或它的 左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
解决思路
根据平衡二叉树的定义，对于每个结点需要满足两个条件：
- 左右子树都是平衡树
- 左右子树的高度差小于等于
1
因此，我们可以采用递归的方式来实现，对于每个结点，返回一个数据结构BalanceValue表示以该结点为根结点的子树是否是平衡树，以及它的高度（叶结点的高度为0）。
代码实现
public class Untitled {
static class Tree {
int size;
Node root;
}
static class Node {
Node parent;
Node left;
Node right;
int value;
}
static class BalanceValue {
boolean isBalance;
int treeHeight;
}
static void insertNode(Tree tree, int value) {
if (tree == null) {
return;
}
Node tNode = tree.root;
//待插入结点的父结点，如果遍历完为空，说明此时是一个空树。
Node pNode = null;
//新的结点。
Node nNode = new Node();
nNode.value = value;
while (tNode != null) {
pNode = tNode;
if (tNode.value > value) {
tNode = tNode.left;
} else {
tNode = tNode.right;
}
}
nNode.parent = pNode;
if (pNode == null) {
tree.root = nNode;
} else if (pNode.value > value) {
pNode.left = nNode;
} else {
pNode.right = nNode;
}
tree.size++;
}
static Tree createBinTree(int p[], int len) {
Tree tree = new Tree();
for (int i = 0; i < len; i++) {
int value = p[i];
insertNode(tree, value);
}
return tree;
}
static BalanceValue isTreeBalance(Node node) {
BalanceValue value = new BalanceValue();
if (node == null) {
value.treeHeight = -1;
value.isBalance = true;
return value;
}
//先确定左子树是否是平衡树。
BalanceValue left = isTreeBalance(node.left);
if (left.isBalance) {
//再确定右子树是否是平衡树。
BalanceValue right = isTreeBalance(node.right);
if (right.isBalance) {
int leftHeight = left.treeHeight;
int rightHeight = right.treeHeight;
//左右的高度差是否小于等于1。
if (Math.abs(leftHeight - rightHeight) <= 1) {
//得到当前结点的高度。
value.treeHeight = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
value.isBalance = true;
return value;
}
}
}
value.isBalance = false;
return value;
}
public static void main(String[] args) {
int p[] = {3, 5, 6, 1, 2, 4, -1, -3, -99, -100};
Tree tree = createBinTree(p, p.length);
System.out.println("平衡树=" + isTreeBalance(tree.root).isBalance);
}
}
运行结果
>> 平衡树=false
更多文章，欢迎访问我的 Android 知识梳理系列：
- Android 知识梳理目录：http://www.jianshu.com/p/fd82d18994ce
- Android 面试文档分享：http://www.jianshu.com/p/8456fe6b27c4
