|
本文轉(zhuǎn)載自http://blog.csdn.net/fightforyourdream/article/details/16843303
?
題目：?
1. 前序、中序、后序遍歷二叉樹(shù)?
2. 層序遍歷二叉樹(shù)?
3. 獲得二叉樹(shù)的深度?
4. 獲得二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)?
5. 判斷兩棵二叉樹(shù)是否為相同的二叉樹(shù)?
6. 判斷二叉樹(shù)是否為平衡二叉樹(shù)?
7. 獲得二叉樹(shù)的葉子節(jié)點(diǎn)個(gè)數(shù)?
8. 獲得二叉樹(shù)第K層上的節(jié)點(diǎn)個(gè)數(shù)?
9. 將二叉查找樹(shù)變?yōu)橛行虻碾p向鏈表?
10. 求二叉樹(shù)中兩個(gè)節(jié)點(diǎn)的最低公共祖先節(jié)點(diǎn)?
11. 求二叉樹(shù)兩個(gè)節(jié)點(diǎn)之間的最大距離?
12. 求從根節(jié)點(diǎn)出發(fā)到node的路徑path?
13. 根據(jù)兩個(gè)遍歷序列重建二叉樹(shù)?
14. 判斷二叉樹(shù)是否為完全二叉樹(shù)?
15.判斷二叉樹(shù)B是不是二叉樹(shù)A的子結(jié)構(gòu)?
16.二叉樹(shù)的鏡像?
17.判斷一個(gè)序列是否是二叉搜索樹(shù)的后序遍歷序列?
18.求二叉樹(shù)中和為某一值的路徑
代碼如下：?
二叉樹(shù)的基本組成：
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
測(cè)試主方法：
import java.util.*;
/**
* 二叉樹(shù)題目匯總
*
* 1、前序、中序、后序遍歷二叉樹(shù)，preOrder1，preOrder2,inOrder1,inOrder2,postOrder1,postOrder2
* 2、層序遍歷二叉樹(shù)，levelOrder1,levelOrder2
* 3、獲得二叉樹(shù)的深度，getDepth
* 4、獲得二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)，getNodesNum
* 5、判斷兩棵二叉樹(shù)是否為相同的二叉樹(shù)，isSameTree
* 6、判斷二叉樹(shù)是否為平衡二叉樹(shù)，isAVL
* 7、獲得二叉樹(shù)的葉子節(jié)點(diǎn)個(gè)數(shù)，getLeafNodeNum
* 8、獲得二叉樹(shù)第K層上的節(jié)點(diǎn)個(gè)數(shù)，getKthLevelNodesNum
* 9、將二叉查找樹(shù)變?yōu)橛行虻碾p向鏈表，convertBST2DLL
* 10、求二叉樹(shù)中兩個(gè)節(jié)點(diǎn)的最低公共祖先節(jié)點(diǎn)，getLastCommonParent
* 11、求二叉樹(shù)兩個(gè)節(jié)點(diǎn)之間的最大距離，getMaxDistance
* 12、求從根節(jié)點(diǎn)出發(fā)到node的路徑path,getNodePath
* 13、根據(jù)兩個(gè)遍歷序列重建二叉樹(shù)，rebuildBinaryTreeByPreAndIn,rebuildBinaryTreeByInAndPost
* 14、判斷二叉樹(shù)是否為完全二叉樹(shù)，isCompleteBinaryTree
*/
@SuppressWarnings("All")
public class TreeDemo {
/*
1
/ 2 3
/ \ 4 5 6
*/
public static void main(String[] args) {
TreeNode r1 = new TreeNode(1);
TreeNode r2 = new TreeNode(2);
TreeNode r3 = new TreeNode(3);
TreeNode r4 = new TreeNode(4);
TreeNode r5 = new TreeNode(5);
TreeNode r6 = new TreeNode(6);
r1.left = r2;
r1.right = r3;
r2.left = r4;
r2.right = r5;
r3.right = r6;
// preOrder1(r1);
// System.out.println("前序遍歷，遞歸");
// preOrder2(r1);
// System.out.println("前序遍歷，迭代");
//
// inOrder1(r1);
// System.out.println("中序遍歷，遞歸");
// inOrder2(r1);
// System.out.println("中序遍歷，迭代");
// postOrder1(r1);
// System.out.println("后序遍歷，遞歸");
// postOrder2(r1);
// System.out.println("后序遍歷，迭代");
// levelOrder1(r1);
// System.out.println("層序遍歷，迭代");
// levelOrder2(r1);
// System.out.println("層序遍歷， 遞歸");
// System.out.println(getDepth1(r1));
// System.out.println(getDepth2(r1));
System.out.println(getNodesNum1(r1));
System.out.println(getNodesNum2(r1));
}
}
1. 前序、中序、后序遍歷二叉樹(shù)
以下分別是前序，中序，后序遍歷二叉樹(shù)的遞歸和迭代解法，具體思路在方法前有說(shuō)明。
/**
* 前序遍歷，遞歸解法
* （1）如果二叉樹(shù)為空，空操作
* （2）如果二叉樹(shù)不為空，訪問(wèn)根節(jié)點(diǎn)，前序遍歷左子樹(shù)，前序遍歷右子樹(shù)
*/
public static void preOrder1(TreeNode root) {
if(root == null) {
return;
}
System.out.print(root.val " ");
preOrder1(root.left);
preOrder1(root.right);
}
* 前序遍歷，迭代
* 用一個(gè)輔助stack，總是把右孩子放進(jìn)棧
*/
public static void preOrder2(TreeNode root) {
if(root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop(); //出棧頂元素
System.out.print(cur.val " ");
// 關(guān)鍵點(diǎn)：要先壓入右孩子，再壓入左孩子，這樣在出棧時(shí)會(huì)先打印左孩子再打印右孩子
if(cur.right != null) {
stack.push(cur.right);
}
if(cur.left != null) {
stack.push(cur.left);
}
}
}
?
/**
* 中序遍歷，遞歸
*/
public static void inOrder1(TreeNode root) {
if(root == null) {
return;
}
inOrder1(root.left);
System.out.print(root.val " ");
inOrder1(root.right);
}
?
/**
* 中序遍歷迭代解法 ，用棧先把根節(jié)點(diǎn)的所有左孩子都添加到棧內(nèi)，
* 然后輸出棧頂元素，再處理?xiàng)ｍ斣氐挠易訕?shù)
* http://www./watch?v=50v1sJkjxoc
*
* 還有一種方法能不用遞歸和棧，基于線索二叉樹(shù)的方法，較麻煩以后補(bǔ)上
* http://www./inorder-tree-traversal-without-recursion-and-without-stack/
*/
public static void inOrder2(TreeNode root) {
if(root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (true) {
while (cur != null) { // 先添加一個(gè)非空節(jié)點(diǎn)所有的左孩子到棧
stack.push(cur);
cur = cur.left;
}
if(stack.isEmpty()) {
break;
}
// 因?yàn)榇藭r(shí)已經(jīng)沒(méi)有左孩子了，所以輸出棧頂元素
cur = stack.pop();
System.out.print(cur.val " ");
cur = cur.right;
}
}
?
/**
* 后序遍歷，遞歸
*/
public static void postOrder1(TreeNode root) {
if(root == null) {
return;
}
postOrder1(root.left);
postOrder1(root.right);
System.out.print(root.val " ");
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
/**
* 后序遍歷，迭代
* 需要用到兩個(gè)棧，分別將左子樹(shù)和右子樹(shù)壓入棧1，再取出第一個(gè)棧中的元素存放到棧2中，完成后序遍歷的逆序輸出
* @param root
*/
public static void postOrder2(TreeNode root) {
if(root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
Stack<TreeNode> out = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
out.push(cur);
if(cur.left != null) {
stack.push(cur.left);
}
if(cur.right != null) {
stack.push(cur.right);
}
}
while (!out.isEmpty()) {
System.out.print(out.pop().val " ");
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
2. 層序遍歷二叉樹(shù)
分別采用迭代和遞歸的方法來(lái)分層遍歷二叉樹(shù)
/**
* 分層遍歷二叉樹(shù)（按層次從上往下，從左往右）迭代
* 相當(dāng)于廣度優(yōu)先搜索，使用隊(duì)列實(shí)現(xiàn)。隊(duì)列初始化，將根節(jié)點(diǎn)壓入隊(duì)列。當(dāng)隊(duì)列不為空，進(jìn)行如下操作：彈出一個(gè)節(jié)點(diǎn)
*/
public static void levelOrder1(TreeNode root) {
if(root == null) {
return;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode cur = queue.removeFirst();
System.out.print(cur.val " ");
if(cur.left != null) {
queue.add(cur.left);
}
if(cur.right != null) {
queue.add(cur.right);
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
/**
* 層序遍歷，遞歸
* 很少有人會(huì)用遞歸去做level traversal
* 基本思想是用一個(gè)大的ArrayList，里面包含了每一層的ArrayList。
* 大的ArrayList的size和level有關(guān)系
*
* 這是我目前見(jiàn)到的最好的遞歸解法！
* http://discuss./questions/49/binary-tree-level-order-traversal#answer-container-2543
*/
public static void levelOrder2(TreeNode root) {
ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
dfs(root, 0, ret);
System.out.print(ret);
}
public static void dfs(TreeNode root, int level, ArrayList<ArrayList<Integer>> ret) {
if(root == null) {
return;
}
if(level >= ret.size()) {
ret.add(new ArrayList<Integer>());
}
ret.get(level).add(root.val); //把節(jié)點(diǎn)值加入到表示那一層的list集合中
dfs(root.left, level 1, ret);
dfs(root.right, level 1, ret);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
3.獲得二叉樹(shù)的深度
獲得二叉樹(shù)深度的遞歸和迭代解法：
/**
* 求二叉樹(shù)的深度（高度） 遞歸解法： O(n)
* （1）如果二叉樹(shù)為空，二叉樹(shù)的深度為0
* （2）如果二叉樹(shù)不為空，二叉樹(shù)的深度 = max(左子樹(shù)深度， 右子樹(shù)深度) 1
*/
public static int getDepth1(TreeNode root) {
if(root == null) {
return 0;
}
int left = getDepth1(root.left);
int right = getDepth1(root.right);
return Math.max(left, right) 1;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
/**
* 求二叉樹(shù)的深度（高度） 迭代解法： O(n)
* 基本思想同LevelOrder，還是用一個(gè)Queue
*/
public static int getDepth2(TreeNode root) {
if(root == null) {
return 0;
}
int depth = 0;
int currentLevelNodes = 1; //當(dāng)前層的節(jié)點(diǎn)數(shù)
int nextLevelNodes = 0; //下一層的節(jié)點(diǎn)數(shù)
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode cur = queue.removeFirst(); //從隊(duì)頭位置開(kāi)始移除
currentLevelNodes--; //當(dāng)前層數(shù)節(jié)點(diǎn)減1
if(cur.left != null) { //當(dāng)前節(jié)點(diǎn)有左子節(jié)點(diǎn)，加入隊(duì)列中
queue.add(cur.left);
nextLevelNodes ; //并將下一層節(jié)點(diǎn)數(shù)加1
}
if(cur.right != null) {
queue.add(cur.right);
nextLevelNodes ;
}
if(currentLevelNodes == 0) { //如果處理完當(dāng)前層的所有節(jié)點(diǎn)
depth ; //深度加1
currentLevelNodes = nextLevelNodes; //初始化當(dāng)前層為下一層
nextLevelNodes = 0;
}
}
return depth;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
4.獲得二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)
遞歸：
/**
* 二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)，遞歸
*/
public static int getNodesNum1(TreeNode root) {
if(root == null) {
return 0;
}
int left = getNodesNum1(root.left);
int right = getNodesNum1(root.right);
return left right 1;
}
/**
* 二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)，迭代
* java用LinkedList來(lái)模擬queue的用法
*/
public static int getNodesNum2(TreeNode root) {
if(root == null) {
return 0;
}
int count = 1;
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode cur = queue.removeFirst();
if(cur.left != null) {
queue.add(cur.left);
count ;
}
if(cur.right != null) {
queue.add(cur.right);
count ;
}
}
return count;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
5.判斷兩棵二叉樹(shù)是否為相同的二叉樹(shù)
/**
* 判斷兩顆二叉樹(shù)是否為相同的二叉樹(shù),遞歸
*/
public static boolean isSameTree1(TreeNode r1, TreeNode r2) {
// 如果兩棵二叉樹(shù)都為空，返回真
if(r1 == null && r2 == null) {
return true;
}
// 如果兩棵二叉樹(shù)一棵為空，另一棵不為空，返回假
else if(r1 == null || r2 == null) {
return false;
}
if(r1.val != r2.val) {
return false;
}
boolean left = isSameTree1(r1.left, r2.left); //分別比較左子樹(shù)和右子樹(shù)是否相等
boolean right = isSameTree1(r1.right, r2.right);
return left && right;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
/**
* 判斷兩顆二叉樹(shù)是否相同，迭代解法
* 分別用兩個(gè)棧來(lái)存儲(chǔ)兩棵樹(shù)，采用前序遍歷的方法依次比較兩顆二叉樹(shù)的各個(gè)節(jié)點(diǎn)的值是否相等，
* 如果不相等直接返回空，相等就繼續(xù)將后面的節(jié)點(diǎn)入棧
*/
public static boolean isSameTree2(TreeNode r1, TreeNode r2) {
if(r1 == null && r2 == null) {
return true;
}
else if(r1 == null || r2 == null) {
return false;
}
Stack<TreeNode> s1 = new Stack<>();
Stack<TreeNode> s2 = new Stack<>();
s1.add(r1);
s2.add(r2);
while (!s1.isEmpty() && !s2.isEmpty()) {
TreeNode n1 = s1.pop();
TreeNode n2 = s2.pop();
if(n1 == null && n2 == null) {
continue;
}
else if(n1!=null && n2 != null && n1.val == n2.val) {
s1.push(n1.right);
s1.push(n1.left);
s2.push(n2.right);
s2.push(n2.left);
}
else {
return false;
}
}
return true;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
6.判斷二叉樹(shù)是否為平衡二叉樹(shù)
/**
* 判斷二叉樹(shù)是不是平衡二叉樹(shù) 遞歸解法：
* （1）如果二叉樹(shù)為空，返回真
* （2）如果二叉樹(shù)不為空，如果左子樹(shù)和右子樹(shù)都是AVL樹(shù)并且左子樹(shù)和右子樹(shù)高度相差不大于1，返回真，其他返回假
*/
public static boolean isAVL(TreeNode root) {
if(root == null) {
return true;
}
if(Math.abs(getDepth1(root.left) - getDepth1(root.right)) > 1) {
return false;
}
return isAVL(root.left) && isAVL(root.right);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
7.獲得二叉樹(shù)中葉子節(jié)點(diǎn)的個(gè)數(shù)
/**
* 求二叉樹(shù)中葉子節(jié)點(diǎn)的個(gè)數(shù)，遞歸
*/
public static int getLeafNodeNum1(TreeNode root) {
if(root == null) {
return 0;
}
if(root.left == null && root.right == null) {
return 1;
}
return getLeafNodeNum1(root.left) getLeafNodeNum1(root.right);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
/**
* 求二叉樹(shù)中葉子節(jié)點(diǎn)的個(gè)數(shù)，迭代
* 基于層序遍歷的思想
*/
public static int getLeafNodeNum2(TreeNode root) {
if(root == null) {
return 0;
}
int count = 0;
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode cur = queue.removeFirst();
if(cur.left == null && cur.right == null) {
count ;
}
if(cur.left != null) {
queue.add(cur.left);
}
if(cur.right != null) {
queue.add(cur.right);
}
}
return count;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
8.求二叉樹(shù)第K層節(jié)點(diǎn)的個(gè)數(shù)
/**
* 求二叉樹(shù)第K層節(jié)點(diǎn)的個(gè)數(shù)
* （1）如果二叉樹(shù)為空或者k<1返回0
* （2）如果二叉樹(shù)不為空并且k==1，返回1
* （3）如果二叉樹(shù)不為空且k>1，返回root左子樹(shù)中k-1層的節(jié)點(diǎn)個(gè)數(shù)與root右子樹(shù)k-1層節(jié)點(diǎn)個(gè)數(shù)之和
*
* 求以root為根的k層節(jié)點(diǎn)數(shù)目 等價(jià)于 求以root左孩子為根的k-1層（因?yàn)樯倭藃oot那一層）節(jié)點(diǎn)數(shù)目 加上
* 以root右孩子為根的k-1層（因?yàn)樯倭藃oot那一層）節(jié)點(diǎn)數(shù)目
*
* 所以遇到樹(shù)，先把它拆成左子樹(shù)和右子樹(shù)，把問(wèn)題降解
*/
public static int getKthLevelNodesNum1(TreeNode root, int k) {
if(root == null || k < 1) {
return 0;
}
if(k == 1) {
return 1;
}
int left = getKthLevelNodesNum1(root.left, k-1); //求root左子樹(shù)的k-1層節(jié)點(diǎn)數(shù)
int right = getKthLevelNodesNum1(root.right, k-1);
return left right;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
/**
* 求二叉樹(shù)第K層節(jié)點(diǎn)數(shù)目，迭代
* 利用層序遍歷的思想
*/
public static int getKthLevelNodesNum2(TreeNode root, int k) {
if(root == null || k < 1) {
return 0;
}
if(k == 1) {
return 1;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
int currentLevelNodes = 1;
int nextLevelNodes = 0;
int i = 1;
while (!queue.isEmpty() && i < k) {
TreeNode cur = queue.removeFirst(); //移除隊(duì)頭位置
currentLevelNodes--; //當(dāng)前層節(jié)點(diǎn)數(shù)減1
if(cur.left != null) {
queue.add(cur.left);
nextLevelNodes ;
}
if(cur.right != null) {
queue.add(cur.right);
nextLevelNodes ;
}
if(currentLevelNodes == 0) {
currentLevelNodes = nextLevelNodes;
nextLevelNodes = 0;
i ;
}
}
return currentLevelNodes;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
9.將二叉查找樹(shù)變?yōu)橛行虻碾p鏈表
/**
* 將二叉查找樹(shù)變?yōu)橛行虻碾p向鏈表 要求不能創(chuàng)建新節(jié)點(diǎn)，只調(diào)整指針。
* 節(jié)點(diǎn)的左即為鏈表前一節(jié)點(diǎn)，右即為鏈表后一節(jié)點(diǎn)
* 遞歸解法：
* 參考了http:///questions/11511898/converting-a-binary-search-tree-to-doubly-linked-list#answer-11530016
* 感覺(jué)是最清晰的遞歸解法，但要注意遞歸完，root會(huì)在鏈表的中間位置，因此要手動(dòng)
* 把root移到鏈表頭或鏈表尾
*/
public static TreeNode convertBST2DLL1(TreeNode root) {
root = convertBST2DLLSub(root);
// root會(huì)在鏈表的中間位置，因此要手動(dòng)把root移到鏈表頭
while (root.left != null) {
root = root.left;
}
return root;
}
/**
* 遞歸轉(zhuǎn)換二叉查找樹(shù)為雙向鏈表(DLL)
*/
public static TreeNode convertBST2DLLSub(TreeNode root) {
if(root == null || (root.left == null && root.right == null)) {
return root;
}
TreeNode tmp = null;
if(root.left != null) { //處理左子樹(shù)
tmp = convertBST2DLLSub(root.left);
while (tmp.right != null) { //尋找最右節(jié)點(diǎn)
tmp = tmp.right;
}
tmp.right = root; //把左子樹(shù)處理后結(jié)果和root連接
root.left = tmp;
}
if(root.right != null) { //處理右子樹(shù)
tmp = convertBST2DLLSub(root.right);
while (tmp.left != null) { //尋找最左節(jié)點(diǎn)
tmp = tmp.left;
}
tmp.left = root; //把右子樹(shù)處理后結(jié)果和root連接
root.right = tmp;
}
return root;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
/**
* 二叉查找樹(shù)轉(zhuǎn)換為雙向鏈表，迭代解法
* 基本思想同中序遍歷二叉樹(shù)
*/
public static TreeNode convertBST2DLL2(TreeNode root) {
if(root == null) {
return null;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root; //指向當(dāng)前正在處理的節(jié)點(diǎn)
TreeNode old = null; //前一節(jié)點(diǎn)
TreeNode head = null; //雙向鏈表的頭結(jié)點(diǎn)
while (true) {
while (cur != null) { //將所有左節(jié)點(diǎn)全部入棧
stack.push(cur);
cur = cur.left;
}
if(stack.isEmpty()) {
break;
}
//由于此時(shí)沒(méi)有左孩子了，所以輸出棧頂元素
cur = stack.pop();
if(old != null) {
old.right = cur;
}
if(head == null) { //第一個(gè)結(jié)點(diǎn)為雙向鏈表頭結(jié)點(diǎn)
head = cur;
}
old = cur; //更新old
cur = cur.right; //準(zhǔn)備處理右子樹(shù)
}
return head;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
10.求二叉樹(shù)中兩個(gè)節(jié)點(diǎn)的最低公共祖先節(jié)點(diǎn)
/**
* 求二叉樹(shù)中兩個(gè)節(jié)點(diǎn)的最低公共祖先節(jié)點(diǎn)
* 遞歸解法：
* （1）如果兩個(gè)節(jié)點(diǎn)分別在根節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)，則返回根節(jié)點(diǎn)
* （2）如果兩個(gè)節(jié)點(diǎn)都在左子樹(shù)，則遞歸處理左子樹(shù)；如果兩個(gè)節(jié)點(diǎn)都在右子樹(shù)，則遞歸處理右子樹(shù)
*/
public static TreeNode getLastCommonParent(TreeNode root, TreeNode n1, TreeNode n2) {
if(findNode(root.left, n1)) { //如果節(jié)點(diǎn)n1在樹(shù)的左子樹(shù)
if(findNode(root.right, n2)) { //節(jié)點(diǎn)n2在樹(shù)的右子樹(shù)
return root;
}
else { //節(jié)點(diǎn)n2也在左子樹(shù)，則遞歸處理左子樹(shù)
return getLastCommonParent(root.left, n1, n2);
}
}
else { //n1在右子樹(shù)
if(findNode(root.left, n2)) {
return root;
}
else {
return getLastCommonParent(root.right, n1, n2);
}
}
}
//遞歸判斷一個(gè)節(jié)點(diǎn)是否在樹(shù)里
public static boolean findNode(TreeNode root, TreeNode n) {
if(root == null || n == null) {
return false;
}
if(root == n) {
return true;
}
//先嘗試在左子樹(shù)里查找
boolean found = findNode(root.left, n);
if(!found) { //如果不在左子樹(shù)中
found = findNode(root.right, n); //在右子樹(shù)中查找
}
return found;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
//求二叉樹(shù)中兩個(gè)節(jié)點(diǎn)的最低公共祖先節(jié)點(diǎn)，更加簡(jiǎn)便的遞歸方法
public static TreeNode getLastCommonParent1(TreeNode root, TreeNode n1, TreeNode n2) {
if(root == null) {
return null;
}
//如果兩者有一個(gè)與root 相同
if(root.equals(n1) || root.equals(n2)) {
return root;
}
TreeNode commonInLeft = getLastCommonParent1(root.left, n1, n2);
TreeNode commonInRight = getLastCommonParent1(root.right, n1, n2);
//如果一個(gè)在左子樹(shù)找到一個(gè)在右子樹(shù)找到，則為root
if(commonInLeft != null && commonInRight != null) {
return root;
}
//其他情況要不然在左子樹(shù)要不然在右子樹(shù)
if(commonInLeft != null) {
return commonInLeft;
}
return commonInRight;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
/**
* 獲取兩個(gè)節(jié)點(diǎn)的最低公共祖先節(jié)點(diǎn)，復(fù)雜度比較低，也是面試官想看到的解法
* 算法思路：
* 1）分別獲得一條從根節(jié)點(diǎn)到指定節(jié)點(diǎn)的路徑，該過(guò)程需要輔助空間List來(lái)存放路徑上的節(jié)點(diǎn)
* 2）求這兩條路徑的最后一個(gè)橡膠的節(jié)點(diǎn)即為題目想要找到的節(jié)點(diǎn)
* 得到兩條路在最壞情況下的時(shí)間復(fù)雜度是O(n),通常情況下兩條路徑的長(zhǎng)度是O(logn)
*/
public static TreeNode getLastCommonParent2(TreeNode root, TreeNode n1, TreeNode n2) {
if(root == null || n1 == null || n2 == null) {
return null;
}
ArrayList<TreeNode> path1 = new ArrayList<>();
getNodePath(root, n1, path1);
ArrayList<TreeNode> path2 = new ArrayList<>();
getNodePath(root, n2, path2);
return getCommonNode(path1, path2);
}
//獲得兩條路徑的最后一個(gè)公共節(jié)點(diǎn)
public static TreeNode getCommonNode(List<TreeNode> path1, List<TreeNode> path2) {
int i = 0;
TreeNode res = null;
while (i < path1.size() && i < path2.size()) {
if(path1.get(i) == path2.get(i)) {
res = path1.get(i);
i ;
}
else {
break;
}
}
return res;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
11.求二叉樹(shù)中節(jié)點(diǎn)的最大距離
/**
* 求二叉樹(shù)中節(jié)點(diǎn)的最大距離 即二叉樹(shù)中相距最遠(yuǎn)的兩個(gè)節(jié)點(diǎn)之間的距離。 (distance / diameter)
* 遞歸解法：
* （1）如果二叉樹(shù)為空，返回0，同時(shí)記錄左子樹(shù)和右子樹(shù)的深度，都為0
* （2）如果二叉樹(shù)不為空，最大距離要么是左子樹(shù)中的最大距離，要么是右子樹(shù)中的最大距離，
* 要么是左子樹(shù)節(jié)點(diǎn)中到根節(jié)點(diǎn)的最大距離 右子樹(shù)節(jié)點(diǎn)中到根節(jié)點(diǎn)的最大距離，
*
* 同時(shí)記錄左子樹(shù)和右子樹(shù)節(jié)點(diǎn)中到根節(jié)點(diǎn)的最大距離。
*
* http://www.cnblogs.com/miloyip/archive/2010/02/25/1673114.html
*
* 計(jì)算一個(gè)二叉樹(shù)的最大距離有兩個(gè)情況:
情況A: 路徑經(jīng)過(guò)左子樹(shù)的最深節(jié)點(diǎn)，通過(guò)根節(jié)點(diǎn)，再到右子樹(shù)的最深節(jié)點(diǎn)。
情況B: 路徑不穿過(guò)根節(jié)點(diǎn)，而是左子樹(shù)或右子樹(shù)的最大距離路徑，取其大者。
只需要計(jì)算這兩個(gè)情況的路徑距離，并取其大者，就是該二叉樹(shù)的最大距離
*/
public static Result getMaxDistance(TreeNode root) {
if(root == null) {
Result empty = new Result(0, -1); // 目的是讓調(diào)用方 1 后，把當(dāng)前的不存在的 (NULL) 子樹(shù)當(dāng)成最大深度為 0
return empty;
}
//計(jì)算出左右子樹(shù)分別最大距離
Result lmd = getMaxDistance(root.left);
Result rmd = getMaxDistance(root.right);
Result res = new Result();
res.maxDepth = Math.max(lmd.maxDepth, rmd.maxDepth) 1; //計(jì)算最大深度
//取情況A和情況B中較大值
res.maxDistance = Math.max(lmd.maxDepth rmd.maxDepth, Math.max(lmd.maxDistance, rmd.maxDistance));
return res;
}
private static class Result {
int maxDistance;
int maxDepth;
public Result() {
}
public Result(int maxDistance, int maxDepth) {
this.maxDistance = maxDistance;
this.maxDepth = maxDepth;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
12.把從根節(jié)點(diǎn)出發(fā)到node節(jié)點(diǎn)的路徑所有經(jīng)過(guò)的節(jié)點(diǎn)添加到路徑path中
/**
* 把從根節(jié)點(diǎn)出發(fā)到node節(jié)點(diǎn)的路徑所有經(jīng)過(guò)的節(jié)點(diǎn)添加到路徑path中
*/
public static boolean getNodePath(TreeNode root, TreeNode node, ArrayList<TreeNode> path) {
if(root == null) {
return false;
}
path.add(root); //先將根節(jié)點(diǎn)添加到路徑中
if(root == node) {
return true;
}
boolean found = getNodePath(root.left, node, path); //在左子樹(shù)中找node節(jié)點(diǎn)
if(!found) { //左子樹(shù)中沒(méi)有node節(jié)點(diǎn)，在右子樹(shù)中查找
found = getNodePath(root.right, node, path);
}
if(!found) { //如果左右子樹(shù)中都不存在node節(jié)點(diǎn)，則將之前加到path中的root節(jié)點(diǎn)刪除
path.remove(root);
}
return found;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
13.重建二叉樹(shù)
/**
* 根據(jù)前序遍歷序列和中序遍歷序列重建二叉樹(shù)
*/
public static TreeNode rebuildBinaryTreeByPreAndIn(List<TreeNode> preOrder, List<TreeNode> inOrder) {
TreeNode root = null; //定義二叉樹(shù)根節(jié)點(diǎn)
List<TreeNode> leftPreOrder; //左子樹(shù)前序遍歷序列
List<TreeNode> rightPreOrder; //右子樹(shù)前序遍歷序列
List<TreeNode> leftInOrder; //左子樹(shù)中序遍歷序列
List<TreeNode> rightInOrder; //右子樹(shù)中序遍歷序列
int preNum = 0;
int inNum = 0;
if((!preOrder.isEmpty()) && (!inOrder.isEmpty())) {
root = preOrder.get(0); //前序遍歷的第一個(gè)節(jié)點(diǎn)即為根節(jié)點(diǎn)
//根據(jù)root的位置，可以確定inOrder左邊的是左子樹(shù)序列，右邊的是右子樹(shù)序列
inNum = inOrder.indexOf(root); //找到root在inOrder中的位置
leftInOrder = inOrder.subList(0, inNum); //左子樹(shù)中序遍歷序列
rightInOrder = inOrder.subList(inNum 1, inOrder.size()); //右子樹(shù)中序遍歷序列
preNum = leftInOrder.size(); //前序序列的分割點(diǎn)
leftPreOrder = preOrder.subList(1, preNum 1);
rightPreOrder = preOrder.subList(preNum 1, preOrder.size());
root.left = rebuildBinaryTreeByPreAndIn(leftPreOrder, leftInOrder); // root的左子樹(shù)就是preorder和inorder的左側(cè)區(qū)間而形成的樹(shù)
root.right = rebuildBinaryTreeByPreAndIn(rightPreOrder, rightInOrder);
}
return root;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
/**
* 根據(jù)中序和后序遍歷序列重建二叉樹(shù)
*/
public static TreeNode rebuildBinaryTreeByInAndPost(List<TreeNode> inOrder, List<TreeNode> postOrder) {
TreeNode root = null; //新建根節(jié)點(diǎn)
List<TreeNode> leftInOrder;
List<TreeNode> rightInOrder;
List<TreeNode> leftPostOrder;
List<TreeNode> rightPostOrder;
int inNum = 0;
int postNum = 0;
if((inOrder.size() != 0) && (postOrder.size() != 0)) {
root = postOrder.get(postOrder.size()-1); //后序遍歷序列的最后一個(gè)節(jié)點(diǎn)即為根節(jié)點(diǎn)
//由root節(jié)點(diǎn)的位置可以分割中序遍歷序列
inNum = inOrder.indexOf(root);
leftInOrder = inOrder.subList(0, inNum);
rightInOrder = inOrder.subList(inNum 1, inOrder.size());
postNum = leftInOrder.size(); //后序遍歷序列的左右子樹(shù)分割點(diǎn)
leftPostOrder = postOrder.subList(0, postNum);
rightPostOrder = postOrder.subList(postNum, postOrder.size());
root.left = rebuildBinaryTreeByInAndPost(leftInOrder, leftPostOrder);
root.right = rebuildBinaryTreeByInAndPost(rightInOrder, rightPostOrder);
}
return root;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
14.判斷二叉樹(shù)是否為完全二叉樹(shù)
/**
* 判斷二叉樹(shù)是否為完全二叉樹(shù)，迭代
* 若設(shè)二叉樹(shù)的深度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，
第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉樹(shù)。
有如下算法，按層次（從上到下，從左到右）遍歷二叉樹(shù)，當(dāng)遇到一個(gè)節(jié)點(diǎn)的左子樹(shù)為空時(shí)，
則該節(jié)點(diǎn)右子樹(shù)必須為空，且后面遍歷的節(jié)點(diǎn)左右子樹(shù)都必須為空，否則不是完全二叉樹(shù)。
*/
public static boolean isCompleteBinaryTree1(TreeNode root) {
if(root == null) {
return false;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
boolean mastHaveNoChild = false;
boolean result = false;
while (!queue.isEmpty()) {
TreeNode cur = queue.remove(); //隊(duì)列先進(jìn)先出
if(mastHaveNoChild){ // 已經(jīng)出現(xiàn)了有空子樹(shù)的節(jié)點(diǎn)了，后面出現(xiàn)的必須為葉節(jié)點(diǎn)（左右子樹(shù)都為空）
if(cur.left != null || cur.right != null) {
result = false;
break;
}
}
else {
if(cur.left == null && cur.right != null) { //如果左子樹(shù)為空，右子樹(shù)非空則說(shuō)明不是完全二叉樹(shù)
result = false;
break;
}
else if(cur.left != null && cur.right == null) { //如果左子樹(shù)非空，右子樹(shù)為空，則左子節(jié)點(diǎn)不能有左右子樹(shù)
mastHaveNoChild = true;
queue.add(cur.left);
}
else if(cur.left != null && cur.right != null) { //如果左右子孩子都非空，則加入隊(duì)列繼續(xù)循環(huán)
queue.add(cur.left);
queue.add(cur.right);
}
else { // 如果左右子樹(shù)都為空，則后面的必須也都為空子樹(shù)
mastHaveNoChild = true;
}
}
}
return result;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
/**
* 判斷二叉樹(shù)是否是完全二叉樹(shù)，遞歸解法
*/
public static boolean isCompleteBinaryTree2(TreeNode root) {
return isCompleteTree(root).height != -1;
}
public static Pair isCompleteTree(TreeNode root) {
if(root == null) {
return new Pair(0, true);
}
Pair left = isCompleteTree(root.left);
Pair right = isCompleteTree(root.right);
//如果左樹(shù)是滿樹(shù)，且左右子樹(shù)同高度，則是唯一可能形成滿樹(shù)（右樹(shù)也是滿樹(shù)）的情況
if(left.isFull && left.height == right.height) {
return new Pair(1 left.height, right.isFull);
}
//左樹(shù)非滿，但右樹(shù)是滿樹(shù)，且左樹(shù)比右樹(shù)高度高1
if(right.isFull && left.height == right.height 1) {
return new Pair(left.height 1, false);
}
//其他情況都不是完全二叉樹(shù)
return new Pair(-1, false);
}
private static class Pair {
int height; //樹(shù)的高度
boolean isFull; //是否是滿樹(shù)
public Pair(int height, boolean isFull) {
this.height = height;
this.isFull = isFull;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
15.判斷二叉樹(shù)B是不是二叉樹(shù)A的子結(jié)構(gòu)
/**
* 兩顆二叉樹(shù)A,B，判斷B是不是A的子樹(shù)
*
* 解題思路：
* 1）在樹(shù)A中找到樹(shù)B的根節(jié)點(diǎn)值一樣的節(jié)點(diǎn)R
* 2）判斷A中以R為根節(jié)點(diǎn)的子樹(shù)是不是包含和樹(shù)B一樣的結(jié)構(gòu)
*/
public static boolean isSubTree(TreeNode root1, TreeNode root2) {
boolean result = false;
if(root1 != null && root2 != null) { //兩顆二叉樹(shù)都不為空的時(shí)候
//如果在A中找到和B的根節(jié)點(diǎn)值相同的節(jié)點(diǎn)R，則調(diào)用doseTree1HasTree2做第二步判斷
if(root1.val == root2.val) {
result = doseTree1HasTree2(root1, root2);
}
//如果在A中沒(méi)有找到和B的根節(jié)點(diǎn)相同的節(jié)點(diǎn)R，則遞歸遍歷左右子樹(shù)尋找
if(!result) {
result = isSubTree(root1.left, root2);
}
if(!result) {
result = isSubTree(root1.right, root2);
}
}
return result;
}
//第二步，判斷A中以R為根節(jié)點(diǎn)的子樹(shù)是不是和樹(shù)B有相同的結(jié)構(gòu)
public static boolean doseTree1HasTree2(TreeNode root1, TreeNode root2) {
//這里一定是root2的判斷在前，若先判斷root1則可能會(huì)出現(xiàn)root1和root2都為空的情況，此時(shí)返回的是false答案將會(huì)是錯(cuò)誤的，所以一定要先判斷root2
if(root2 == null) {
return true;
}
if(root1 == null) {
return false;
}
if(root1.val != root2.val) {
return false;
}
//遞歸判斷他們左右子節(jié)點(diǎn)的值是否相同
return doseTree1HasTree2(root1.left, root2.left) &&
doseTree1HasTree2(root1.right, root2.right);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
16.二叉樹(shù)的鏡像
/**
* 求一棵二叉樹(shù)的鏡像
*
* 解題過(guò)程：（遞歸）
* 先前序遍歷這棵樹(shù)的每個(gè)節(jié)點(diǎn)，如果遍歷到的節(jié)點(diǎn)有子節(jié)點(diǎn)，則交換兩個(gè)子節(jié)點(diǎn)（同時(shí)也是交換了它的左右子樹(shù)），
* 當(dāng)交換完所有非葉子結(jié)點(diǎn)的子節(jié)點(diǎn)以后，就得到了樹(shù)的鏡像
* 該解法會(huì)破壞原二叉樹(shù)的結(jié)構(gòu)
*/
public static void mirrorTree(TreeNode root) {
//如果該樹(shù)為空樹(shù)或者是只有一個(gè)節(jié)點(diǎn)的樹(shù)，則直接返回
if(root == null || (root.left == null && root.right == null)) {
return;
}
//交換左右子節(jié)點(diǎn)
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
if(root.left != null) { //如果左子節(jié)點(diǎn)存在
//遞歸遍歷左子樹(shù)
mirrorTree(root.left);
}
if(root.right != null) {
mirrorTree(root.right);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
/**
* 求一棵二叉樹(shù)的鏡像
*
* 迭代解法
* 仍然采用前序遍歷的方法，用棧來(lái)實(shí)現(xiàn)
*/
public static void mirrorTree2(TreeNode root) {
if(root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
TreeNode temp = cur.left;
cur.left = cur.right;
cur.right = temp;
if(cur.right != null) { //前序遍歷，先壓入右節(jié)點(diǎn)，再壓入左節(jié)點(diǎn)
stack.push(cur.right);
}
if(cur.left != null) {
stack.push(cur.left);
}
}
}
?
//不改變?cè)鏄?shù)的迭代解法
public static TreeNode mirrorTree3(TreeNode root) {
if(root == null) {
return null;
}
TreeNode newRoot = new TreeNode(root.val);
Stack<TreeNode> stack = new Stack<>();
Stack<TreeNode> newStack = new Stack<>();
stack.push(root);
newStack.push(newRoot);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
TreeNode newCur = newStack.pop();
if(cur.right != null) {
stack.push(cur.right);
newCur.left = new TreeNode(cur.right.val);
newStack.push(newCur.left);
}
if(cur.left != null) {
stack.push(cur.left);
newCur.right = new TreeNode(cur.left.val);
newStack.push(newCur.right);
}
}
return newRoot;
}
17.判斷一個(gè)序列是否是二叉搜索樹(shù)的后序遍歷序列
/**
* 判斷一個(gè)序列是否是二叉搜索樹(shù)的后序遍歷序列
*
* 根據(jù)后序遍歷序列的規(guī)則，最后一個(gè)元素即根元素，比根元素小的是左子樹(shù)，大的是右子樹(shù)，然后遞歸判斷
*
* @param start 起始索引下標(biāo)
* @param end 結(jié)束索引下標(biāo)
*/
public static boolean verifySequenceOfBST(int[] sequence, int start, int end) {
if(sequence == null || start < 0 || end <= 0) {
return false;
}
int root = sequence[end]; //根節(jié)點(diǎn)就是最后一個(gè)元素
//在二叉搜索樹(shù)中左子樹(shù)的節(jié)點(diǎn)都比右子樹(shù)小
int i = 0;
for (; i < end; i ) {
if(sequence[i] > root) {
break;
}
}
//在二叉搜索樹(shù)中右子樹(shù)的節(jié)點(diǎn)大于根節(jié)點(diǎn)
int j = i; //右子樹(shù)的第一個(gè)元素（序列中的元素）
for (; j < end; j ) {
if(sequence[j] < root) {
return false;
}
}
//判斷左子樹(shù)是不是二叉搜索樹(shù)
boolean left = true;
i--;
if(i > 0) {
left = verifySequenceOfBST(sequence, 0, i);
}
//判斷右子樹(shù)是不是二叉搜索樹(shù)
boolean right = true;
i ;
if(i < end) {
right = verifySequenceOfBST(sequence, i, end-1);
}
return (left && right);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
18.求二叉樹(shù)中和為某一值的路徑
/**
* 求二叉樹(shù)中和為某一值的路徑
* 題目描述：從樹(shù)的根節(jié)點(diǎn)開(kāi)始往下一直到葉節(jié)點(diǎn)所經(jīng)過(guò)的節(jié)點(diǎn)形成一條路徑
*
* 解題思路：
* 用前序遍歷的方式訪問(wèn)某一節(jié)點(diǎn)時(shí)，把該節(jié)點(diǎn)加入到路徑上，并且累加該節(jié)點(diǎn)的值。
* 如果該節(jié)點(diǎn)為葉子節(jié)點(diǎn)并且路徑中節(jié)點(diǎn)值的和剛好等于輸入的整數(shù)，則當(dāng)前路徑符合要求，可以打印出來(lái)；
* 如果當(dāng)前節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，則繼續(xù)訪問(wèn)它的子節(jié)點(diǎn)。
* 當(dāng)前節(jié)點(diǎn)訪問(wèn)結(jié)束后，遞歸函數(shù)自動(dòng)回到它的父節(jié)點(diǎn)。（實(shí)際可以用棧來(lái)滿足）
* 因此在退出之前要在路徑上刪除當(dāng)前節(jié)點(diǎn)，并且減去當(dāng)前節(jié)點(diǎn)的值，以確保返回父節(jié)點(diǎn)時(shí)路徑剛好是從根節(jié)點(diǎn)到父節(jié)點(diǎn)的路徑
*/
public static void findPath(TreeNode root, int sum) {
if(root == null) {
return;
}
int currentSum = 0;
//用java里面LinkedList的add和removeLast方法實(shí)現(xiàn)棧的先進(jìn)后出特性，這樣方便和面打印路徑
LinkedList<Integer> path = new LinkedList<>(); //用于存儲(chǔ)路徑
findPathTemp(root, sum, path, currentSum);
}
public static void findPathTemp(TreeNode root, int sum, LinkedList<Integer> path, int currentSum) {
currentSum = root.val;
path.addLast(root.val);
//如果是葉子節(jié)點(diǎn)，并且路徑上節(jié)點(diǎn)值的和等于輸入的整數(shù)
boolean isLeaf = false;
if(root.left == null && root.right == null) {
isLeaf = true;
}
if(currentSum == sum && isLeaf) {
System.out.println("A path is found:");
for (int i = 0; i < path.size(); i ) {
System.out.printf("%d\t", path.get(i));
}
System.out.println();
}
//如果不是葉子節(jié)點(diǎn)，則遍歷它的子節(jié)點(diǎn)
if(root.left != null) {
findPathTemp(root.left, sum, path, currentSum);
}
if(root.right != null) {
findPathTemp(root.right, sum, path, currentSum);
}
//在返回父節(jié)點(diǎn)之前，在路徑上刪除當(dāng)前節(jié)點(diǎn)
path.removeLast();
}
來(lái)源：http://www./content-4-145301.html
|
