1.二叉樹相關(guān)遍歷 二叉搜索樹(有序:根大于左子樹小于右子樹)相關(guān)遍歷 （迭代和遞歸）
適當(dāng)?shù)木毦毷郑涗浺幌隆?br>
System.out.println("中序遍歷結(jié)果 = " + inorderTraversal(treeNode));
System.out.println("前序遍歷結(jié)果 = " + inorderTraversal1(treeNode));
System.out.println("后序遍歷結(jié)果 = " + inorderTraversal2(treeNode));
System.out.println("層序遍歷結(jié)果 = " + levelOrder(treeNode));
System.out.println("二叉樹的最大深度 = " + maxDepthInIteration(treeNode));
System.out.println("對稱二叉樹 = " + isSymmetric(treeNode));
System.out.println("二叉樹路徑總合 = " + hasPathSum(treeNode, 7));
System.out.println("從中序與后序遍歷序列構(gòu)造二叉樹 中序顯示= " + inorderTraversal(buildTree(inorder, postorder)));
System.out.println("二叉樹的最近公共祖先 = " + lowestCommonAncestor(treeNode, new TreeNode(2),new TreeNode(3)));
System.out.println("二叉樹的序列化與反序列化 = " + serialize(treeNode));
System.out.println("二叉樹的反序列化 中序顯示= " + inorderTraversal(deserialize("1,2,#,#,3,#,#,")));
System.out.println("是否是二叉搜索樹 = " + isValidBST(treeNode));
System.out.println("searchBST 二叉樹搜索樹搜索某個節(jié)點= " + searchBST(treeNode,3));
System.out.println("二叉樹搜索樹插入某個節(jié)點 中序顯示= " + inorderTraversal(insertIntoBST(treeNode,4)));
package com.test.algorithm;
import javafx.util.Pair;
import java.util.*;
/**
* @author rs
* @version 1.0
* @date 2020/2/18 0018 10:33
* 二叉樹中序遍歷 迭代
* 1
* 2 3 左右根
*/
public class OrderTraversalInBinaryTree {
/*************************************************中序遍歷**************************************************/
/**
* 中序遍歷 迭代
* @param root
* @return
*/
public static List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null) {
return list;
}
Stack<TreeNode> stack = new Stack<>(); // 棧先進后出
TreeNode cur = root;
while(cur != null || !stack.isEmpty()) { // 8.curr = null, statck.size = 1 12.cur != null 18.cur = null, stack.size = 0
while(cur != null) {
stack.push(cur); // 進棧 1.將整個cur推進stack里面 3.將左節(jié)點推進stack，此時stack.size = 2 13.將3,null,null推進棧
cur = cur.left; // 2.將cur的left賦值給cur，cur就成為了左節(jié)點 4.此時的cur的左節(jié)點為null 14.cur = null
}
cur = stack.pop(); // 出棧 5.因為先進后出，所以cur=root的左節(jié)點（這里需要有空間想象） 9.將之前的root彈出來 15.cur = 3
list.add(cur.val); // 6.此時val = 2,因為在第4步整個cur的左節(jié)點都為null，如果它有右節(jié)點也是排在2后面的 10. 添加根節(jié)點1 16. 添加根節(jié)點3
cur = cur.right; // 7.cur = null 11. cur = 3,null,null 17.cur = null
}
return list;
}
/**
* 中序遍歷 遞歸
* @param root
* @return
*/
List<Integer> inorderTraversalForTterationList = new ArrayList<>();
public List<Integer> inorderTraversalForTteration(TreeNode root) {
if (root != null) {
inorderTraversalForTteration(root.left);
inorderTraversalForTterationList.add(root.val);
inorderTraversalForTteration(root.right);
}
return inorderTraversalForTterationList;
}
/*************************************************前序遍歷**************************************************/
/**
* 前序遍歷 迭代 根左右
* @param root
* @return
*
*/
public static List<Integer> inorderTraversal1(TreeNode root) {
//
List<Integer> list = new ArrayList<>();
if (root == null) {
return list;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()) {
while(cur != null) {
stack.push(cur);
list.add(cur.val);
cur = cur.left;
}
cur = stack.pop();
cur = cur.right;
}
return list;
}
/**
* 前序遍歷 遞歸版
* @param args
*/
private List<Integer> ans = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
// 遞歸版
if(root == null) return ans;
ans.add(root.val);
if(root.left != null) preorderTraversal(root.left);
if(root.right != null) preorderTraversal(root.right);
return ans;
}
/***********************************************后序遍歷****************************************************/
/**
* 后序遍歷 迭代 左右根
* @param root
* @return
*/
public static List<Integer> inorderTraversal2(TreeNode root) {
//
List<Integer> list = new ArrayList<>();
if (root == null) {
return list;
}
Stack<TreeNode> s = new Stack<>();
s.push(root);
while( !s.isEmpty() ) {
TreeNode node = s.pop(); // 1.出棧root
if(node.left != null) {
s.push(node.left); // 2.進棧 2,null,null
}
if(node.right != null) {
s.push(node.right); // 3. 進棧 3,null,null
}
list.add(0, node.val); // 從最后插入依次插入 1 3 2 打印出來就是2 1 3
}
return list;
}
/**
* 后序遍歷 遞歸
*/
List<Integer> postorderTraversalList = new LinkedList<>();
public List<Integer> postorderTraversal(TreeNode root) {
if(root == null)
return ans;
postorderTraversal(root.left);
postorderTraversal(root.right);
postorderTraversalList.add(root.val);
return ans;
}
/***********************************************層序遍歷*************************************************/
/**
*
* @param root
* @return
*/
public static List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> listList = new ArrayList<>();
if(root == null) {
return listList;
}
Queue<TreeNode> queue = new LinkedList<>(); // 練習(xí)了上面的題目，知道queue是先進先出就ok
queue.add(root);
while(!queue.isEmpty()) {
int size = queue.size();
List<Integer> list = new ArrayList<>();
while(size > 0) {
TreeNode tempNode = queue.poll();
list.add(tempNode.val);
if(tempNode.left != null) {
queue.add(tempNode.left);
}
if(tempNode.right != null) {
queue.add(tempNode.right);
}
size--; // 從上到下，從左到右一個一個遍歷
}
listList.add(list);
}
return listList;
}
/***********************************************練習(xí)1：二叉樹的最大深度*************************************************/
/**
* 遞歸解法
* @param root
* @return
*/
public static int maxDepth(TreeNode root) {
if (root == null){
return 0;
} else {
int left_depth = maxDepth(root.left);
int right_depth = maxDepth(root.right);
return Math.max(left_depth, right_depth) + 1;
}
}
/**
* 迭代解法
* @param root
* @return
* 1.pair類似于map k,v結(jié)構(gòu)
* 2.不同點：stack.peek 不改變棧的值(不刪除棧頂?shù)闹?，pop會把棧頂?shù)闹祫h除。 相同點：大家都返回棧頂?shù)闹怠? * 總結(jié)：left進棧，加深度（出現(xiàn)右節(jié)點的左子節(jié)點）， right:出棧
*/
public static int maxDepthInIteration(TreeNode root) {
int depth = 0;
//1.初始化一個棧
Stack<Pair<TreeNode, Integer>> stack = new Stack<>();
TreeNode p = root;
int current_depth = 0;
while(p !=null || !stack.isEmpty()){
if(p!=null){
stack.push(new Pair(p,++ current_depth)); // 1. stack=k:1,2,3 v:1 4. stack=2,null,null 2 14.3,null,null 2
depth = Math.max(depth,current_depth); // 2. d=1 5. d=2 15. d=2
p = p.left; // 3.stack = 2,null,null 6.stack null,null,null size=2 16.null,null,null
}else{
current_depth = stack.isEmpty()? 0:stack.peek().getValue(); // 7. cd=2 10. cd=1 17.cd=2
p = stack.pop().getKey(); // 8.stack 2,null,null 11. stack 1,2,3 18.3,null,null
p = p.right; // 9. stack null,null,null 12. stack 3,null,nul 19. null,null,null 此時p=null,stack.isEmpty=true
}
}
return depth;
}
/***********************************************練習(xí)2：對稱二叉樹*************************************************/
/**
* 迭代 對稱是指對應(yīng)數(shù)值相對，不僅是結(jié)構(gòu)相對
* @param root
* @return
*/
public static boolean isSymmetric(TreeNode root) {
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
q.add(root);
while (!q.isEmpty()) {
TreeNode t1 = q.poll();
TreeNode t2 = q.poll();
if (t1 == null && t2 == null) continue;
if (t1 == null || t2 == null) return false;
if (t1.val != t2.val) return false;
// 順序有講究
q.add(t1.left);
q.add(t2.right);
q.add(t1.right);
q.add(t2.left);
}
return true;
}
/*********************************************練習(xí)3：二叉樹路徑總合***************************************/
/**
* 給定一個二叉樹和一個目標(biāo)和，判斷該樹中是否存在根節(jié)點到葉子節(jié)點的路徑，這條路徑上所有節(jié)點值相加等于目標(biāo)和。
* @param root
* @param sum
* @return 遞歸解法
* 思路： 1 1.num - 1,2.num -2,3.左null, 4.右走||判斷,null 5.回到2,null,null,在回到1，2，3 6. 回到3,null,null
* 2 3 7.走null,null,null兩次，回到3，null,null 結(jié)束
* null null null null
*/
public static boolean hasPathSum(TreeNode root, int sum) {
if(root == null) {
return false;
}
if(root.val == sum && root.left == null && root.right == null) {
return true;
}
sum -= root.val;
return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
}
/*****************************************總結(jié)練習(xí)1：從中序與后序遍歷序列構(gòu)造二叉樹*********************************/
/**
* 例如，給出
*
* 中序遍歷 inorder = [9,3,15,20,7]
* 后序遍歷 postorder = [9,15,7,20,3]
* 返回如下的二叉樹：
*
* 3
* / \
* 9 20
* / \
* 15 7
* 關(guān)鍵點: 1.兩個數(shù)組的下標(biāo) 0 和 len-1，先找后序的根，根據(jù)根來區(qū)分中序的左子樹和右子樹
* 2.左節(jié)點遞歸(0~根-1，0~后序左+左子樹-1）
* 3.右節(jié)點遞歸（左子樹+1~中序右邊，后序左+左子樹~后序右-1）
*
*/
private static int[] inorder = {15,9, 12, 3, 15, 20, 7 }; // 中序遍歷 確定左右節(jié)點
private static int[] postorder = { 15,12, 9, 15, 7, 20, 3 }; // 后序遍歷 確定根節(jié)點
public static TreeNode buildTree(int[] inorder, int[] postorder) {
TreeNode root = create(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1);
return root;
}
private static TreeNode create(int[] inorder, int[] postorder, int inLeft, int inRight, int postLeft, int postRight) {
if(postLeft > postRight){
return null; // 16. 退回到上一顆數(shù)15,null,null
}
TreeNode treeNode = new TreeNode(postorder[postRight]); // 1. 先找后序最后一個數(shù)，就是根節(jié)點 10.根節(jié)點為后序數(shù)組中的9 14.根是15
int k = 0;
for(int i = inLeft; i <= inRight; i++){ // 2.遍歷一下中序數(shù)組
if(inorder[i] == postorder[postRight]){ // 3. 如果數(shù)據(jù)里的值 = 根節(jié)點
k = i; // 4.根節(jié)點下標(biāo)賦值給k = 3 11.根節(jié)點下標(biāo)1 15. 0
break;
}
}
int numLeft = k - inLeft; // 5.（左子樹的長度 = 3）在中序遍歷中找到根節(jié)點，左邊就是左子樹，右邊就是右子樹 12. 1
// 6. 左節(jié)點遞歸(0~根-1，0~后序左+左子樹-1） 確定中序遍歷的左子樹的范圍，0~2， 13. 0~1-1，0~0+1-1
// 7.根據(jù)后序遍歷特性：（左右根），根據(jù)第6步知道左子樹的范圍是0~2，所以在后序數(shù)組中的左子樹范圍也是0~2，并且知道下標(biāo)2是根節(jié)點，值為9
// 8.postLeft + numLeft - 1 19.回到9,null,null
treeNode.left = create(inorder, postorder, inLeft, k - 1, postLeft, postLeft + numLeft - 1);
// 17. 右節(jié)點遞歸（左子樹+1~中序右邊，后序左+左子樹~后序右-1）此時左子樹為15,null,null 它的左子樹長度為0，所以要找左子樹右節(jié)點：會return
treeNode.right = create(inorder, postorder, k + 1, inRight, postLeft + numLeft, postRight - 1); // 20 回到9,15,null 繼續(xù)找左子樹12這個根節(jié)點
return treeNode; // 18.執(zhí)行此步奏
}
/*****************************************總結(jié)練習(xí)2：二叉樹的最近公共祖先*********************************/
/**
* 給定一個二叉樹, 找到該樹中兩個指定節(jié)點的最近公共祖先。
*
* 百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結(jié)點 p、q，最近公共祖先表示為一個結(jié)點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節(jié)點也可以是它自己的祖先）。”
*
* 示例 1:
* 3
* 5 1
* 6 2 0 8
* 7 4
* 輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
* 輸出: 3
* 解釋: 節(jié)點 5 和節(jié)點 1 的最近公共祖先是節(jié)點 3。
* @param root
* @param p
* @param q
* @return
*/
public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//遞歸出口
if (root == null || root == p || root == q) {
return root;
}
//去該節(jié)點的左子樹上找
TreeNode left = lowestCommonAncestor(root.left, p, q);
//去該節(jié)點的右子樹上找
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left == null) {
//左子樹上沒有，說明在右子樹上
return right;
} else if (right == null) {
//右子樹上沒有，說明在左子樹上
return left;
}
//左右均有，說明該節(jié)點即為最近公共祖先
return root;
}
/*****************************************總結(jié)練習(xí)3：二叉樹的序列化與反序列化*********************************/
/**
* 二叉樹的數(shù)的序列化和反序列化，二叉樹實際是存儲在內(nèi)存中的，一旦斷電或者是關(guān)機，二叉樹的數(shù)據(jù)就會在內(nèi)存中丟失。
* 所以我們需要將二叉樹的數(shù)據(jù)保存下來，這個過程叫做持久化或者序列化；將二叉樹的數(shù)據(jù)保存到了磁盤之后，還需要將
* 磁盤中的二叉樹的數(shù)據(jù)加載到內(nèi)存中去，這過程叫做反序列化。
*
* 解決思路：節(jié)點和節(jié)點之間使用,來分隔，空節(jié)點使用#來表示，為什么需要使用#來分隔？
* 假如所有的節(jié)點都是相同的值，且不使用分隔符號，結(jié)構(gòu)不同也會序列化為相同的結(jié)果
*/
public static String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
encode(root, sb);
return sb.toString();
}
private static void encode(TreeNode node, StringBuilder sb) {
if (node == null) {
sb.append("#,");
} else {
sb.append(node.val);
sb.append(",");
encode(node.left, sb);
encode(node.right, sb);
}
}
// Decodes your encoded data to tree.
public static TreeNode deserialize(String data) {
String[] vs = data.split(",");
return decode(vs, new int[]{0});
}
private static TreeNode decode(String[] vs, int[] idx) {
if (vs.length == 0 || idx[0] >= vs.length) {
return null;
}
String s = vs[idx[0]];
idx[0]++;
if ("#".equals(s)) {
return null;
} else {
int val = Integer.valueOf(s);
TreeNode node = new TreeNode(val);
node.left = decode(vs, idx);
node.right = decode(vs, idx);
return node;
}
}
/*****************************************訓(xùn)練1：是否二叉樹搜索樹*********************************/
/**
* 二叉搜索樹具有以下性質(zhì)：每個節(jié)點中的值必須大于（或等于）其左側(cè)子樹中的任何值，但小于（或等于）其右側(cè)子樹中的任何值。
* 關(guān)鍵點：只要有任何一顆樹不滿足條件，在遞歸下去或者遞歸回來時將結(jié)果層層return
*/
static Integer pre = null;
public static boolean isValidBST(TreeNode root) {
return invailInorderTraversal(root);
}
private static boolean invailInorderTraversal(TreeNode root){
if(root == null){
return true;
}
if(!invailInorderTraversal(root.left)){
return false;
}
if(pre != null && root.val <= pre){ // 走左子樹 false時，根節(jié)點<= 左節(jié)點 走右子樹false時：右根節(jié)點<=右根父節(jié)點
return false;
}
pre = root.val;
if(!invailInorderTraversal(root.right)){
return false;
}
return true;
}
/*****************************************訓(xùn)練1：二叉樹搜索樹搜索某個節(jié)點*********************************/
/**
* 給定二叉搜索樹（BST）的根節(jié)點和一個值。 你需要在BST中找到節(jié)點值等于給定值的節(jié)點。
* 返回以該節(jié)點為根的子樹。 如果節(jié)點不存在，則返回 NULL。
* @param root
* @param val
* @return
*/
public static TreeNode searchBST(TreeNode root, int val) {
if (root == null) {
return null;
}
if (root.val == val) {
return root;
}
else if (root.val > val) {
return searchBST(root.left, val);
}
else {
return searchBST(root.right, val);
}
}
/*****************************************訓(xùn)練2：二叉樹搜索樹插入某個節(jié)點*********************************/
public static TreeNode insertIntoBST(TreeNode root, int val) {
if(root == null) {
return new TreeNode(val);
}
// 大右小左
if(root.val < val) {
root.right = insertIntoBST(root.right, val);
}else if(root.val > val) {
root.left = insertIntoBST(root.left, val);
}
return root;
}
public static TreeNode insertIntoBST1(TreeNode root, int val) {
if(root==null) return new TreeNode(val);
TreeNode node = root;
while(true)
{
if(node.val<val)
{
if(node.right!=null) node = node.right;
else{
node.right = new TreeNode(val);
break;
}
}
else{
if(node.left!=null) node = node.left;
else{
node.left = new TreeNode(val);
break;
}
}
}
return root;
}
/*****************************************訓(xùn)練3：二叉樹搜索樹刪除某個節(jié)點*********************************/
public static TreeNode deleteNode(TreeNode root, int key) {
if (!containNode(root, key)) {
return root;
}
if (root.val == key) {
if (root.left == null) {
return root.right;
} else if (root.right == null) {
return root.left;
}
TreeNode successor = findMin(root.right); // 找到右邊最小的作為頭節(jié)點
successor.right = delMin(root.right); //刪除掉這個最小節(jié)點,右邊就遍歷好了，在添加左邊就行了
successor.left = root.left;//
return successor;
} else if (root.val < key) {
root.right = deleteNode(root.right, key);
return root;
} else {
root.left = deleteNode(root.left, key);
return root;
}
}
private static boolean containNode(TreeNode treeNode, int key) {
if (treeNode == null) {
return false;
}
if (treeNode.val == key) {
return true;
} else if (treeNode.val > key) {
return containNode(treeNode.left, key);
} else {
return containNode(treeNode.right, key);
}
}
/*
* return a treeNode whose key is the minimum in the tree
*/
private static TreeNode findMin(TreeNode treeNode) {
TreeNode cur = treeNode;
while (cur != null) {
if (cur.left == null) {
return cur;
}
cur = cur.left;
}
return cur;
}
/*
* return a treeNode after deleting its treeNode whose key is the minimum
*/
private static TreeNode delMin(TreeNode treeNode) {
if (treeNode.left == null) {
return treeNode.right;
}
treeNode.left = delMin(treeNode.left);
return treeNode;
}
/*****************************************進階1：N叉樹的前序遍歷*********************************/
/**
*
* @param root
* @return
*/
public static List<Integer> preorder(Node root) {
/*
思路：前序遍歷是根左右，先遍歷根節(jié)點然后按順序遞歸遍歷孩子節(jié)點，當(dāng)沒有孩子節(jié)點時返回
*/
List<Integer> res=new ArrayList<>();
if (root==null)
{
return res;
}
preorder(root,res);
return res;
}
private static void preorder(Node node,List<Integer> res)
{
res.add(node.val);
List<Node> childList=node.children;
if (childList.size()==0)
{
return;
}else {
for (int i = 0; i < childList.size(); i++) {
preorder(childList.get(i),res);
}
}
}
/***********************************************main*************************************************/
public static void main(String[] args) {
TreeNode treeNode = new TreeNode(1);
treeNode.left = new TreeNode(2);
treeNode.right = new TreeNode(3);
System.out.println("中序遍歷結(jié)果 = " + inorderTraversal(treeNode));
System.out.println("前序遍歷結(jié)果 = " + inorderTraversal1(treeNode));
System.out.println("后序遍歷結(jié)果 = " + inorderTraversal2(treeNode));
System.out.println("層序遍歷結(jié)果 = " + levelOrder(treeNode));
System.out.println("二叉樹的最大深度 = " + maxDepthInIteration(treeNode));
System.out.println("對稱二叉樹 = " + isSymmetric(treeNode));
System.out.println("二叉樹路徑總合 = " + hasPathSum(treeNode, 7));
System.out.println("從中序與后序遍歷序列構(gòu)造二叉樹 中序顯示= " + inorderTraversal(buildTree(inorder, postorder)));
System.out.println("二叉樹的最近公共祖先 = " + lowestCommonAncestor(treeNode, new TreeNode(2),new TreeNode(3)));
System.out.println("二叉樹的序列化與反序列化 = " + serialize(treeNode));
System.out.println("二叉樹的反序列化 中序顯示= " + inorderTraversal(deserialize("1,2,#,#,3,#,#,")));
System.out.println("是否是二叉搜索樹 = " + isValidBST(treeNode));
System.out.println("searchBST 二叉樹搜索樹搜索某個節(jié)點= " + searchBST(treeNode,3));
System.out.println("二叉樹搜索樹插入某個節(jié)點 中序顯示= " + inorderTraversal(insertIntoBST(treeNode,4)));
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
class Node {
int val;
List<Node> children;
Node(int x, List<Node> children) {
val = x;
children = children;
}
}
歡迎關(guān)注我的微信公眾號<搜索：汀雨筆記>，會首發(fā)一些最新文章哦！
下面是我的個人網(wǎng)站：http://ransongv587.com
image
