1.二叉树相关遍历 二叉搜索树(有序:根大于左子树小于右子树)相关遍历 （迭代和递归）
适当的练练手，记录一下。
System.out.println("中序遍历结果 = " + inorderTraversal(treeNode));
System.out.println("前序遍历结果 = " + inorderTraversal1(treeNode));
System.out.println("后序遍历结果 = " + inorderTraversal2(treeNode));
System.out.println("层序遍历结果 = " + levelOrder(treeNode));
System.out.println("二叉树的最大深度 = " + maxDepthInIteration(treeNode));
System.out.println("对称二叉树 = " + isSymmetric(treeNode));
System.out.println("二叉树路径总合 = " + hasPathSum(treeNode, 7));
System.out.println("从中序与后序遍历序列构造二叉树 中序显示= " + 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 二叉树搜索树搜索某个节点= " + searchBST(treeNode,3));
System.out.println("二叉树搜索树插入某个节点 中序显示= " + 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.将左节点推进stack，此时stack.size = 2 13.将3,null,null推进栈
cur = cur.left; // 2.将cur的left赋值给cur，cur就成为了左节点 4.此时的cur的左节点为null 14.cur = null
}
cur = stack.pop(); // 出栈 5.因为先进后出，所以cur=root的左节点（这里需要有空间想象） 9.将之前的root弹出来 15.cur = 3
list.add(cur.val); // 6.此时val = 2,因为在第4步整个cur的左节点都为null，如果它有右节点也是排在2后面的 10. 添加根节点1 16. 添加根节点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<>(); // 练习了上面的题目，知道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;
}
/***********************************************练习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结构
* 2.不同点：stack.peek 不改变栈的值(不删除栈顶的值)，pop会把栈顶的值删除。 相同点：大家都返回栈顶的值。
* 总结：left进栈，加深度（出现右节点的左子节点）， 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;
}
/***********************************************练习2：对称二叉树*************************************************/
/**
* 迭代 对称是指对应数值相对，不仅是结构相对
* @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;
}
/*********************************************练习3：二叉树路径总合***************************************/
/**
* 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
* @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 结束
* 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);
}
/*****************************************总结练习1：从中序与后序遍历序列构造二叉树*********************************/
/**
* 例如，给出
*
* 中序遍历 inorder = [9,3,15,20,7]
* 后序遍历 postorder = [9,15,7,20,3]
* 返回如下的二叉树：
*
* 3
* / \
* 9 20
* / \
* 15 7
* 关键点: 1.两个数组的下标 0 和 len-1，先找后序的根，根据根来区分中序的左子树和右子树
* 2.左节点递归(0~根-1，0~后序左+左子树-1）
* 3.右节点递归（左子树+1~中序右边，后序左+左子树~后序右-1）
*
*/
private static int[] inorder = {15,9, 12, 3, 15, 20, 7 }; // 中序遍历 确定左右节点
private static int[] postorder = { 15,12, 9, 15, 7, 20, 3 }; // 后序遍历 确定根节点
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. 退回到上一颗数15,null,null
}
TreeNode treeNode = new TreeNode(postorder[postRight]); // 1. 先找后序最后一个数，就是根节点 10.根节点为后序数组中的9 14.根是15
int k = 0;
for(int i = inLeft; i <= inRight; i++){ // 2.遍历一下中序数组
if(inorder[i] == postorder[postRight]){ // 3. 如果数据里的值 = 根节点
k = i; // 4.根节点下标赋值给k = 3 11.根节点下标1 15. 0
break;
}
}
int numLeft = k - inLeft; // 5.（左子树的长度 = 3）在中序遍历中找到根节点，左边就是左子树，右边就是右子树 12. 1
// 6. 左节点递归(0~根-1，0~后序左+左子树-1） 确定中序遍历的左子树的范围，0~2， 13. 0~1-1，0~0+1-1
// 7.根据后序遍历特性：（左右根），根据第6步知道左子树的范围是0~2，所以在后序数组中的左子树范围也是0~2，并且知道下标2是根节点，值为9
// 8.postLeft + numLeft - 1 19.回到9,null,null
treeNode.left = create(inorder, postorder, inLeft, k - 1, postLeft, postLeft + numLeft - 1);
// 17. 右节点递归（左子树+1~中序右边，后序左+左子树~后序右-1）此时左子树为15,null,null 它的左子树长度为0，所以要找左子树右节点：会return
treeNode.right = create(inorder, postorder, k + 1, inRight, postLeft + numLeft, postRight - 1); // 20 回到9,15,null 继续找左子树12这个根节点
return treeNode; // 18.执行此步奏
}
/*****************************************总结练习2：二叉树的最近公共祖先*********************************/
/**
* 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
*
* 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
*
* 示例 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
* 解释: 节点 5 和节点 1 的最近公共祖先是节点 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;
}
//去该节点的左子树上找
TreeNode left = lowestCommonAncestor(root.left, p, q);
//去该节点的右子树上找
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left == null) {
//左子树上没有，说明在右子树上
return right;
} else if (right == null) {
//右子树上没有，说明在左子树上
return left;
}
//左右均有，说明该节点即为最近公共祖先
return root;
}
/*****************************************总结练习3：二叉树的序列化与反序列化*********************************/
/**
* 二叉树的数的序列化和反序列化，二叉树实际是存储在内存中的，一旦断电或者是关机，二叉树的数据就会在内存中丢失。
* 所以我们需要将二叉树的数据保存下来，这个过程叫做持久化或者序列化；将二叉树的数据保存到了磁盘之后，还需要将
* 磁盘中的二叉树的数据加载到内存中去，这过程叫做反序列化。
*
* 解决思路：节点和节点之间使用,来分隔，空节点使用#来表示，为什么需要使用#来分隔？
* 假如所有的节点都是相同的值，且不使用分隔符号，结构不同也会序列化为相同的结果
*/
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;
}
}
/*****************************************训练1：是否二叉树搜索树*********************************/
/**
* 二叉搜索树具有以下性质：每个节点中的值必须大于（或等于）其左侧子树中的任何值，但小于（或等于）其右侧子树中的任何值。
* 关键点：只要有任何一颗树不满足条件，在递归下去或者递归回来时将结果层层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时，根节点<= 左节点 走右子树false时：右根节点<=右根父节点
return false;
}
pre = root.val;
if(!invailInorderTraversal(root.right)){
return false;
}
return true;
}
/*****************************************训练1：二叉树搜索树搜索某个节点*********************************/
/**
* 给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。
* 返回以该节点为根的子树。 如果节点不存在，则返回 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);
}
}
/*****************************************训练2：二叉树搜索树插入某个节点*********************************/
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;
}
/*****************************************训练3：二叉树搜索树删除某个节点*********************************/
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); // 找到右边最小的作为头节点
successor.right = delMin(root.right); //删除掉这个最小节点,右边就遍历好了，在添加左边就行了
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) {
/*
思路：前序遍历是根左右，先遍历根节点然后按顺序递归遍历孩子节点，当没有孩子节点时返回
*/
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("中序遍历结果 = " + inorderTraversal(treeNode));
System.out.println("前序遍历结果 = " + inorderTraversal1(treeNode));
System.out.println("后序遍历结果 = " + inorderTraversal2(treeNode));
System.out.println("层序遍历结果 = " + levelOrder(treeNode));
System.out.println("二叉树的最大深度 = " + maxDepthInIteration(treeNode));
System.out.println("对称二叉树 = " + isSymmetric(treeNode));
System.out.println("二叉树路径总合 = " + hasPathSum(treeNode, 7));
System.out.println("从中序与后序遍历序列构造二叉树 中序显示= " + 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 二叉树搜索树搜索某个节点= " + searchBST(treeNode,3));
System.out.println("二叉树搜索树插入某个节点 中序显示= " + 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;
}
}
欢迎关注我的微信公众号<搜索：汀雨笔记>，会首发一些最新文章哦！
下面是我的个人网站：http://ransongv587.com
image
