面試算法代碼知識梳理系列
- 插入排序
- 希爾排序
- 選擇排序
- 冒泡排序
- 計(jì)數(shù)排序
- 基數(shù)排序
- 歸并排序
- 快速排序
- 雙向掃描的快速排序
- 堆排序
- 替換字符串中的空格
- 輸入一個(gè)字符串健爬，打印出該字符串的所有排列
- 第一個(gè)只出現(xiàn)一次的字符
- 翻轉(zhuǎn)句子
- 計(jì)算字符串之間的最短距離
- 查找字符串中的最長重復(fù)子串
- 求長度為
N的字符串的最長回文子串 - 將字符串中的
*移到前部，并且不改變非*的順序 - 不開辟用于交換的空間璧函，完成字符串的逆序
C++ - 最短摘要生成
- 最長公共子序列
- 二維數(shù)組的整數(shù)查找
- 旋轉(zhuǎn)數(shù)組中的最小數(shù)字（旋轉(zhuǎn)數(shù)組中的最大數(shù)字）
- 調(diào)整數(shù)組使奇數(shù)位于偶數(shù)之前
- 找出數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字
- 找到最小的
k個(gè)數(shù) - 連續(xù)子數(shù)組的最大和
- 連續(xù)子數(shù)組的最大和（二維）
- 求數(shù)組當(dāng)中的逆序?qū)?/li>
- 在遞增排序的數(shù)組中，查找指定數(shù)字出現(xiàn)的個(gè)數(shù)
- 查找數(shù)組中只出現(xiàn)一次的兩個(gè)數(shù)字
- 在遞增排序的數(shù)組中鸭叙，查找和為
s的兩個(gè)數(shù) - 輸入一個(gè)正數(shù)
s醋界，打印出所有和為s的連續(xù)正數(shù)序列 - 數(shù)組當(dāng)中的最大最小值
- 求數(shù)組當(dāng)中的最長遞增子序列（求數(shù)組當(dāng)中的最長遞減子序列）
- 區(qū)間重合判斷
- 一個(gè)整數(shù)數(shù)組，長度為
n凳兵，將其分為m份杈绸，使各份的和相等帖蔓，求m的最大值
- 普通二分查找
- 查找關(guān)鍵字第一次出現(xiàn)的位置
- 查找關(guān)鍵字最后一次出現(xiàn)的位置
- 查找小于關(guān)鍵字的最大數(shù)字出現(xiàn)的位置
- 查找大于關(guān)鍵字的最小數(shù)字出現(xiàn)的位置
- 新建鏈表
- 反轉(zhuǎn)鏈表（遞歸和非遞歸實(shí)現(xiàn)）
- 獲得鏈表倒數(shù)第
k個(gè)結(jié)點(diǎn) - 獲得鏈表的中間結(jié)點(diǎn)
- 刪除鏈表結(jié)點(diǎn)
- 交換鏈表結(jié)點(diǎn)
- 建立二叉查找樹
- 刪除二叉查找樹中指定元素
- 非遞歸遍歷二叉查找樹（先序遍歷、中序遍歷瞳脓、后序遍歷）
面試算法知識梳理(11) - 二叉樹相關(guān)算法第一部分
- 遞歸遍歷二叉樹（先序遍歷塑娇、中序遍歷、后序遍歷）
- 分層打印二叉樹
- 打印二叉樹的第
n層 - 統(tǒng)計(jì)二叉樹葉結(jié)點(diǎn)的個(gè)數(shù)
- 統(tǒng)計(jì)二叉樹的高度
- 獲得二叉樹的鏡像
- 判斷元素是否存在于二叉樹中
- 打印二叉樹中和為
s的路徑 - 獲得二叉樹的最大距離
- 判斷二叉樹是否是平衡樹
- 將二叉樹轉(zhuǎn)換成為鏈表
- 判斷數(shù)組是否為二叉樹的后序遍歷
- 判斷某樹是否是另一棵樹的子樹
- 根據(jù)前序和中序序列重建二叉樹
一劫侧、概述
- 獲得二叉樹的鏡像
- 判斷元素是否存在于二叉樹中
- 打印二叉樹中和為
s的路徑 - 獲得二叉樹的最大距離
- 判斷二叉樹是否是平衡樹
二埋酬、代碼實(shí)現(xiàn)
2.1 獲得二叉樹的鏡像
代碼實(shí)現(xiàn)
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;
//待插入結(jié)點(diǎn)的父結(jié)點(diǎn)，如果遍歷完為空烧栋，說明此時(shí)是一個(gè)空樹写妥。
Node pNode = null;
//新的結(jié)點(diǎn)。
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);
//遍歷完左子樹后审姓，打印根結(jié)點(diǎn)珍特，最后遍歷右子樹。
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("- 轉(zhuǎn)換前 -");
printInOrder(tree.root);
swapTree(tree.root);
System.out.println("- 轉(zhuǎn)換后 -");
printInOrder(tree.root);
}
}
運(yùn)行結(jié)果
- 轉(zhuǎn)換前 -
-3
-1
1
2
3
4
5
6
- 轉(zhuǎn)換后 -
6
5
4
3
2
1
-1
-3
2.2 判斷元素是否存在于二叉樹中
代碼實(shí)現(xiàn)
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;
//待插入結(jié)點(diǎn)的父結(jié)點(diǎn)邑跪，如果遍歷完為空次坡，說明此時(shí)是一個(gè)空樹呼猪。
Node pNode = null;
//新的結(jié)點(diǎn)画畅。
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));
}
}
運(yùn)行結(jié)果
>> 5 is in tree=true
>> 9 is in tree=false
2.3 打印二叉樹中和為 s 的路徑
問題描述
輸入一個(gè)整數(shù)和一棵二叉樹，打印出和與輸入整數(shù)相等的所有路徑谚赎，從樹的根結(jié)點(diǎn)開始往下訪問一直到葉結(jié)點(diǎn)所經(jīng)過的所有結(jié)點(diǎn)形成一條路徑淫僻。
代碼實(shí)現(xiàn)
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;
//待插入結(jié)點(diǎn)的父結(jié)點(diǎn)，如果遍歷完為空壶唤，說明此時(shí)是一個(gè)空樹雳灵。
Node pNode = null;
//新的結(jié)點(diǎn)。
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;
//如果是葉結(jié)點(diǎn)闸盔，并且和滿足要求悯辙，那么打印出所有的路徑。
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);
}
//當(dāng)其左右子樹都遍歷完之后，將當(dāng)前結(jié)點(diǎn)出棧躲撰。
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);
}
}
運(yùn)行結(jié)果
2
5
4
2.4 獲得二叉樹的最大距離
問題描述
二叉樹距離 指的是兩個(gè) 葉結(jié)點(diǎn)之間邊的個(gè)數(shù)针贬，計(jì)算一個(gè)二叉樹的最大距離有兩種情況，最終的目的就是要獲得這兩種情況的值拢蛋，并取其最大值作為該結(jié)點(diǎn)的最大距離：
- 路徑經(jīng)過左子樹的最深結(jié)點(diǎn)桦他，通過根結(jié)點(diǎn)，再到右子樹的最深結(jié)點(diǎn)谆棱，在這種情況下快压，最大距離等于左子樹的高度加上右子樹的高度在加上
2。 - 路徑不穿過根結(jié)點(diǎn)垃瞧，而是左子樹或右子樹的最大距離路徑嗓节，在這種情況下，最大距離等于這兩者的最大值皆警。
對于每個(gè)結(jié)點(diǎn)拦宣，定義兩個(gè)額外的屬性，maxDistance表示 以該結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹的最大距離信姓，而maxDepth為 以該結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹到最深結(jié)點(diǎn)的距離鸵隧，對于每個(gè)葉結(jié)點(diǎn)來說，這兩個(gè)值為0意推，而對于每個(gè)非葉結(jié)點(diǎn)來說豆瘫，這兩個(gè)值是通過它的左右孩子結(jié)點(diǎn)的這兩個(gè)屬性計(jì)算出來的。
代碼實(shí)現(xiàn)
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;
//待插入結(jié)點(diǎn)的父結(jié)點(diǎn)菊值，如果遍歷完為空外驱，說明此時(shí)是一個(gè)空樹。
Node pNode = null;
//新的結(jié)點(diǎn)腻窒。
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) {
//如果是空結(jié)點(diǎn)昵宇，那么不需要計(jì)算。
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;
}
//深度為左右孩子結(jié)點(diǎn)的深度最大值+1
node.maxDepth = leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
//(1) 通過根結(jié)點(diǎn)儿子，則選取左子樹的深度+右子樹深度+2
int throughRoot = leftDepth + rightDepth + 2;
//(2) 不通過根結(jié)點(diǎn)瓦哎，則選取左右子樹的距離最大值。
int notThroughRoot = leftDistance > rightDistance ? leftDistance : rightDistance;
//取以上兩者的最大值柔逼，作為該結(jié)點(diǎn)的最大距離屬性。
node.maxDistance = throughRoot > notThroughRoot ? throughRoot : notThroughRoot;
}
static void printInOrder(Node node) {
if (node == null) {
return;
}
printInOrder(node.left);
//遍歷完左子樹后愉适，打印根結(jié)點(diǎn)犯助，最后遍歷右子樹。
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);
}
}
運(yùn)行結(jié)果
>> 最大距離=6
2.5 判斷二叉樹是否是平衡樹
問題描述
平衡二叉樹 具有以下性質(zhì)：它是一棵空樹或它的 左右兩個(gè)子樹的高度差的絕對值不超過1维咸，并且左右兩個(gè)子樹都是一棵平衡二叉樹剂买。
解決思路
根據(jù)平衡二叉樹的定義扑媚，對于每個(gè)結(jié)點(diǎn)需要滿足兩個(gè)條件：
- 左右子樹都是平衡樹
- 左右子樹的高度差小于等于
1
因此，我們可以采用遞歸的方式來實(shí)現(xiàn)雷恃，對于每個(gè)結(jié)點(diǎn)疆股，返回一個(gè)數(shù)據(jù)結(jié)構(gòu)BalanceValue表示以該結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹是否是平衡樹，以及它的高度（葉結(jié)點(diǎn)的高度為0）倒槐。
代碼實(shí)現(xiàn)
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;
//待插入結(jié)點(diǎn)的父結(jié)點(diǎn)旬痹，如果遍歷完為空，說明此時(shí)是一個(gè)空樹讨越。
Node pNode = null;
//新的結(jié)點(diǎn)两残。
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) {
//得到當(dāng)前結(jié)點(diǎn)的高度。
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);
}
}
運(yùn)行結(jié)果
>> 平衡樹=false
更多文章着逐，歡迎訪問我的 Android 知識梳理系列：
- Android 知識梳理目錄：http://www.reibang.com/p/fd82d18994ce
- Android 面試文檔分享：http://www.reibang.com/p/8456fe6b27c4
