硅基计划3.0 学习总结 肆 二叉树
文章目录
一、树与性质
1. 二叉树初识
二叉树指的是不存在>=2度数（子节点个数）的节点，分为左右子树，但是二叉树也有可能是空树
-
完全二叉树：节点编号和节点一一对应，而且如果节点度数是偶数，不存在度为1的节点，如果是偶数，则一定存在一个度为1的节点，如下图所示
-
满二叉树：每个节点除了最后一层以外的节点度数都为2，起始就是完全二叉树的特殊情况
2. 树的表示
树可以有多种表示方法，有双亲表示、孩子表示、孩子兄弟等，对于树的定义不过多细讲了
class Node{
int value;
Node firstChild;
Node NextBrother;
}
3. 二叉树性质
- 如果规定第一层的层数下标是一（意思就是不是用数组那种从零下标开始的叫法），那么第L层的最多有 2 k − 1 2^k-1 2k−1个节点
- 如果规定第一层的深度下标是一，那么深度为K的树节点总共有 2 k − 1 2^k -1 2k−1个节点
- 度为1的节点总比度为0的节点少一个
度数之和是度数为0的节点之和+度为1的节点之和+度为2的节点之和
而且边数比节点数少一个，利用这个性质，我们可以得到这个推论
- 具有n个节点的完全二叉树的深度为 log 2 ( n + 1 ) \log_2 (n+1) log2(n+1)，结果向上取整（比如5.2–>6，5.8–>6）
- 含有n个节点的完全二叉树，如果
i=0，那么它就是根节点，否则如果下标i>0，那么它的双亲下标就是(i-1)/2；同理如果2i+1<n，它的左子树（左孩子）下标是2i+1，否则不存在；同理如果2i+2>n，它的右子树（右孩子）下标是2i+2，否则不存在
二、模拟实现二叉树
二叉树的表示常用的是孩子表示法（一个节点的左右两个子节点）和孩子双亲表示法（除了左右两个子节点还包括自己）
接下来我们模拟实现最常用的孩子表示法
1. 创建二叉树
public class BinaryTree {
static class TreeNode{
int value;
TreeNode left;//左孩子
TreeNode right;//右孩子
public TreeNode(int value) {
this.value = value;
}
}
public TreeNode creatNode(){
TreeNode t1 = new TreeNode(15);
TreeNode t2 = new TreeNode(22);
TreeNode t3 = new TreeNode(34);
TreeNode t4 = new TreeNode(56);
TreeNode t5 = new TreeNode(77);
TreeNode t6 = new TreeNode(99);
//手动连接
//左子树
t1.left = t2;
t1.right = t3;
t2.left = t4;
t2.right = t5;
//右子树
t3.left = t6;
//返回头节点
return t1;
}
//一些操作方法
}
//测试类中
public class Test {
BinaryTree binaryTree = new BinaryTree();
BinaryTree.TreeNode root = binaryTree.creatNode();
}
2.遍历
分为前序——根节点左孩子节点右孩子节点，中序——左跟右，后序——左右根，区别只是遍历的顺序不一样，他们的时间空间复杂度都是O(n)
//前序遍历
public void preOrder(TreeNode root){
if(root == null){
return;
}
System.out.print(root.value+" ");
preOrder(root.left);
preOrder(root.right);
}
//中序遍历
public void inOrder(TreeNode root){
if(root == null){
return;
}
inOrder(root.left);
System.out.print(root.value+" ");
inOrder(root.right);
}
//后序遍历
public void pastOrder(TreeNode root){
if(root == null){
return;
}
pastOrder(root.left);
pastOrder(root.right);
System.out.print((root.value + " "));
}
//测试
//前序遍历
binaryTree.preOrder(root);
System.out.println();
//中序遍历
binaryTree.inOrder(root);
//后序遍历
System.out.println();
binaryTree.pastOrder(root);
这里我就拿前序遍历举例子
3. 求节点个数
我们思路就是利用计数器，或者是子问题思路——左子树节点个数+有子树节点个数，他们的时间空间复杂度都是O(n)
ublic int count = 0;
//计数器法则
public void size(TreeNode root){
if(root == null){
return;
}
count++;
size(root.left);
size(root.right);
}
//子问题法则
public int sizePlus(TreeNode root){
if(root == null){
return 0;
}
return sizePlus(root.left)+sizePlus(root.right)+1;
}
4. 求叶子节点
我们的思路就是如果遇到了叶子节点就++，即当前节点的左右孩子节点都是空，时间空间复杂度都是O(n)
public int getLeafNodeCount(TreeNode root){
if(root == null){
return 0;
}
if(root.left == null && root.right == null){
return 1;
}
return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);
}
5. 求第K层节点个数
我们思路就是第K层是左子树的K-1层+右子树的K-1层
我们让K一直减减，直到K=1的时候，时间空间复杂度都是O(n)
//求第K层节点个数
public int getLevelCount(TreeNode root,int k){
if(root == null){
return 0;
}
if(k == 1){
return 1;
}
return getLevelCount(root.left,k-1)+getLevelCount(root.right,k-1);
}
6. 获取二叉树的高度（深度）
我们思路就是左右两个子树求出深度，谁的值比较大就取谁，最后再加上一（根节点），时间复杂度是O(n)，空间复杂度是O(logN)
//求二叉树深度
public int getHeight(TreeNode root){
if(root == null){
return 0;
}
return Math.max(getHeight(root.left),getHeight(root.right))+1;
}
7. 检测指定值是否存在于二叉树中
我们的思路就是先判断根节点是不是我们要找的值，不是就递归，如果左子树没有，就去判断右子树，时间复杂度O(n)，空间复杂度O(logN)
//检测值是否存在
public TreeNode find(TreeNode root,int value){
if(root == null){//终止情况
return null;
}
if(root.value == value){//检测根节点情况
return root;
}
TreeNode ret = find(root.left,value);//检查左子树
if(ret != null){
return ret;//找到了直接返回，下面语句不用进行了
}
ret = find(root.right,value);//左子树找不到，找右子树
if(ret != null){
return ret;//找到了直接返回
}
return null;//找不到语句到这里
}
三. 小试牛刀
1. 检查两棵树是否相同
题目链接
两棵树你要想等，首先我们要比较根节点，你想，如果根节点的左子树是空的，右子树不为空，它们就不可能是一样的，包括左子树不为空，右子树为空也是一样的
我们这样比较是比较的结构是否一样，如果结构是一样的，那我们就去比较根节点的值一不一样，如果不一样，也是直接不用去比较子树了，直接返回false就好
此时呢，我们的结构是一样的，根节点的值也是一样的，那我们就递归根节点的左子树和右子树，我们要保证在子树中，前一棵树左子树要和后一棵树右子树是一样的，同理前一棵树右子树要和后一棵树右子树是一样的
此时如果递归到最后的空节点，我们认为也是一样的
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p != null && q == null || p == null && q != null){
return false;
}
if(p == null && q == null){
return true;
}
if(p.val != q.val){
return false;
}
return isSameTree(p.left,q.left)&&isSameTree(p.right,p.right);
}
}
2. 树的子树判断
题目链接
这题的思想其实和我们刚刚的差不多，我们第一题的判断两棵树是否相同的代码就可以到这一题调用了
先判断当前的树是否和题目给的子树相同，不相同我们去递归左子树和右子树
class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if(root == null){
return false;
}
if(isSameTree(root,subRoot)){
return true;
}
return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
}
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p != null && q == null || p == null && q != null) {
return false;
}
//走到这里的情况是什么？ 要么2个都是空 要么要个都不是空
if( p == null && q == null) {
return true;
}
if(p.val != q.val) {
return false;
}
//走到这里 p != null && q != null && p.val == q.val
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
}
3. 子树左右翻转
题目链接
这题思路就是遍历到一个节点就交换左右，一直遍历完就好了
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null){
return null;
}
//交换
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
//递归
invertTree(root.left);
invertTree(root.right);
//返回当前的根节点
return root;
}
}
这里还给出子问题思路
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null){
return null;
}
//每次递归存储当前根节点值
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
}
这里相当于是从最下面一层开始交换，一直交换到最上面一层
4. 前序遍历
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null){
return list;
}
//先把当前根节点的值添加进去
list.add(root.val);
List<Integer> leftList = preorderTraversal(root.left);
list.addAll(leftList);
List<Integer> rightList = preorderTraversal(root.right);
list.addAll(rightList);
return list;
}
}
–>还可以尝试中序和后续遍历！
5. 判断平衡二叉树
题目链接
这道题的意思就是你要保证子树的高度差不大于1，那我们是不是要保证每一颗子树是平衡的呢
那我们要先判断当前的根节点的左右两个子树高度是否一致，一致就继续递归，关于高度判断的我们之前已经写过了
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null){
return true;
}
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
//必须同时满足才是true否则就进行递归
return Math.abs(leftHeight - rightHeight) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
private int getHeight(TreeNode root){
if(root == null){
return 0;
}
return Math.max(getHeight(root.left),getHeight(root.right))+1;
}
}
但是这个代码存在重复计算，重复计算在高度的计算上，比如小的高度数值老是被重复调用
其实我们在计算高度的时候，左子树假设是2，右子树是0，这个时候已经可以返回false了
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null){
return true;
}
//高度如果是-1就直接返回falase，就不用再重复计算了
return getHeight(root) > 0;
}
private int getHeight(TreeNode root){
if(root == null){
return 0;
}
int leftHeight = getHeight(root.left);
//说明在子树就不平衡了，那我当前的树也不可能平衡，继续返回-1
//我就一直往上返回-1，这样我的当前节点的右子树就不用再重复计算了
if(leftHeight <0){
return -1;
}
//return后下面不用再重复计算了
int rightHeight = getHeight(root.right);
if(rightHeight < 0){
return -1;
}
//return后下面不用再重复计算了
//此时左右子树高度不平衡直接返回-1，高度不可能是-1
if(Math.abs(leftHeight-rightHeight) <= 1){
return Math.max(leftHeight,rightHeight)+1;
}else{
return -1;
}
}
}
6. 对称二叉树
题目链接
这题思路其实不难，就是先判断根节点的值是否一样，再看看根节点是否是空的（比如一个是空的一个不是空）
递归，然后当前根节点的左子树和另一个根节点右子树是否一致，再比较当前根节点的右子树和另一个根节点的左子树是否一致
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null){
return false;
}
return isSymmetricChild(root.left,root.right);
}
private boolean isSymmetricChild(TreeNode left,TreeNode right){
if((left != null && right == null)||(left == null && right != null)){
return false;
}
if(left == null && right == null){
return true;
}
if(left.val != right.val){
return false;
}
return isSymmetricChild(left.left,right.right)&&isSymmetricChild(left.right,right.left);
}
}
7. 字符串构建二叉树
题目链接
为什么这一题就可以只根据前序遍历去创建二叉树呢，因为这一题把空树的情况给你了
这一题思路就是我们字符串每次取一个字符，我们定义i下标取每个字符，看看它是不是'#'，如果不是就创建当前的根节点。这个根节点就是当前的字符，一旦是'#'，我们就不创建根节点，让i继续往后走，最后返回当前的根节点
import java.util.Scanner;
class TreeNode{
public char val;
public TreeNode left;
public TreeNode right;
public TreeNode(char val){
this.val = val;
}
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextLine()) { // 注意 while 处理多个 case
String str = in.nextLine();
TreeNode root = createTree(str);
inOrder(root);
}
}
public static int i = 0;
public static TreeNode createTree(String str){
TreeNode root = null;
if(str.charAt(i) != '#'){
root = new TreeNode(str.charAt(i));
i++;
root.left = createTree(str);//创建左子树
root.right = createTree(str);//创建右子树
}else{
//继续往后遍历
i++;
}
//返回当前根节点
return root;
}
public static void inOrder(TreeNode root){
if(root == null){
return;
}
inOrder(root.left);
System.out.print(root.val+" ");
inOrder(root.right);
}
}
8. 层序遍历
首先我们实现自己的层序遍历
我们不使用递归，我们使用循环来做
层序遍历核心就是我们要把每次从树中取出的元素放入队列中，然后每次弹出队头元素打印就好
//层序遍历-->非递归
public void levelOrder(TreeNode root){
if(root == null){
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
//每一次current指向都会发生变化
TreeNode current = queue.poll();
System.out.print(current.value+" ");
if(current.left != null){
//左子树元素放入队列中
queue.offer(current.left);
}
if(current.right != null){
//右子树元素放入队列中
queue.offer(current.right);
}
}
}
这里有一道题，但是是使用二维队列来写的，因此你要把每一层的遍历结果存起来
题目链接
我们在刚刚代码基础上改进，每一层遍历的时候我怎么知道这是遍历到哪一层了，诶，我们可以使用一个计数器，把当前层数的元素个数计算出来，然后每一层指定弹出几个元素就好
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<>();
if(root == null){
return ret;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);//添加根节点
while(!queue.isEmpty()){//每一层的list
//每一层的队列
List<Integer> list = new ArrayList<>();
int size = queue.size();
while(size != 0){
TreeNode current = queue.poll();
list.add(current.val);//弹出的元素对应放在每一层队列中
if(current.left != null){//放入左子树节点
queue.offer(current.left);
}
if(current.right != null){//放入右子树节点
queue.offer(current.right);
}
size--;
}
ret.add(list);//添加每一层的队列
}
return ret;
}
}
9. 完全二叉树判断
我们思路是这样的，我们先给定一个队列，然后让二叉树节点放入里面，我们再给一个中间变量current等于弹出的元素，放入节点的时候如果队列不为空，就弹出元素
然后去检查弹出的元素current是不是空的，如果是，去检查队列中剩下的元素是不是全为空，定义一个中间变量去查看，但凡有一个不是空的，那它就不是完全二叉树
// 判断⼀棵树是不是完全⼆叉树
public boolean isCompleteTree(TreeNode root){
if(root == null) {
return true;
}
Queue <TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode current = queue.poll();
if(current == null){
break;
}
queue.offer(current.left);
queue.offer(current.right);
}
//此时二叉树全部节点已经放入队列中，即current遇到了null
while(!queue.isEmpty()){
TreeNode temp = queue.peek();
if(temp != null){
return false;
}
queue.poll();
}
return true;
}
10. 找最近的共同祖先
题目链接
这道题意思就是要找当前两个子节点它们的同一个祖先是谁，有分几种情况
那我们的思路是什么呢，首先我们去检查根节点，看看是不是我们要找的p或者是q节点，如果都不是，我们就递归左子树和右子树，如果此时的根节点中，左子树找到了p右子树找到了q，或者是左子树找到了q右子树找到了p，共同祖先还是不变
如果都不满足，前序遍历递归根节点root，如果左子树没找到任何一个，右子树找到了，那么公共祖先就是当前根节点右子树第一个节点，反之如果左子树找到了右子树没找到任何一个，那么公共祖先就是当前根节点左子树第一个节点
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null){
//证明当前递归到了最下面的节点了
return root;
}
if(root == p || root == q){
//排查根节点情况
return root;
}
//用返回值分别接收两个递归结果
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
//说明p和q分布在当前根节点root的左右两侧
if(left != null && right != null){
//显然根节点就是它们共同祖先
return root;
}else if(left != null && right == null){
//说明都分步在当前根节点root的左边，共同祖先就是左子树第一个节点
return left;
}else if(left == null && right != null){
//同理
return right;
}
//最后还是没找到就返回null
return null;
}
}
这个是递归的写法，其实还有非递归的写法，就是我们之前提到过的追击问题，先求出两个节点到根节点的距离差，让后让离得远的节点向根节点先走，然后两个节点再一起行动，如果相遇，这个节点就是它们的共同祖先
但是要怎么保存信息呢，就是记录各个节点到根节点路上的节点信息呢，我们可以用到站，先记录它们各自路径上的节点，再让节点多的先弹出几个节点让两个栈保持平衡，再同时弹出，如果弹出的节点有一致的，则它们共同祖先就是那个一致的节点
//共同祖先非递归写法
//存元素，root表示根节点，node表示当前节点，要存从root到node路径上的节点
private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack){
if(root == null || node == null){
return false;
}
//我们要把所有节点存在栈中，先放入根节点
stack.push(root);
//递归到如果当前根节点等于要找的节点直接返回，此时就不存了
if (root == node){
return true;
}
//递归，检测是不是已经找到了要找的节点，如果找到了就触发flag标记
//如果flag标记为true，下面的if判断可以满足，此时这一层递归又返回true
//一只返回true，直到最开始的根节点
boolean flag = getPath(root.left,node ,stack);
if (flag == true){
return true;
}
//这边也是同理
flag = getPath(root.right,node,stack);
if(flag == true){
return true;
}
stack.pop();
return false;
}
public TreeNode lowestCommonAncestorPlus(TreeNode root,TreeNode p,TreeNode q) {
if (root == null) {
return null;
}
//给定两个栈存节点
Stack<TreeNode> stackP = new Stack<>();
Stack<TreeNode> stackQ = new Stack<>();
getPath(root, p, stackP);
getPath(root, q, stackQ);
int sizeP = stackP.size();
int sizeQ = stackQ.size();
//判断哪个栈元素多一点
int size = sizeP - sizeQ;
if (size < 0) {
size = sizeQ - sizeP;
//说明sizeQ元素多一点，那就让sizeQ先弹出几个元素
while (size != 0) {
stackQ.pop();
size--;
}
} else {
//到这里说明sizeP元素比较多，那就让它先弹出几个元素
while (size != 0) {
stackP.pop();
size--;
}
}
//此时两个栈元素就一样多了
while (!stackP.isEmpty() && !stackQ.isEmpty()) {
//弹出时发现两个栈元素出现了相等的情况，此时直接返回就好了
if (stackP.peek() == stackQ.peek()) {
return stackP.peek();
}
//否则我们就一直弹出，直到栈空
stackP.pop();
stackQ.pop();
}
//到最后啥也没直到直接返回null
return null;
}
11. 根据前序与中序遍历创建二叉树
题目链接
这个题目思路就是我们先在前序遍历去拿到每一个节点，然后在中序遍历中去找到根节点的位置
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTreeChild(preorder,0,inorder,0,inorder.length-1);
}
private TreeNode buildTreeChild(int [] preorder,int preIndex,int [] inorder,int begin,int inend){
//每次递归的时候创建一个根节点
TreeNode root = new TreeNode(preorder[preIndex]);
//寻找根节点下标，每一次递归preIndex都要往后走，寻找下一个根节点下标
int rootIndex = findRootIndex(inorder,inbegin,inend,preorder[preIndex]);
preIndex++;
//递归当前根节点的左子树
root.left = buildTreeChild(preorder,preIndex,inorder,inbegin,rootIndex-1);
root.right = buildTreeChild(preorder,preIndex,inorder,rootIndex+1,inend);
//最后返回当前的根节点
return root;
}
//在数组区间内寻找每次一指定根节点key
private int findRootIndex(int [] inorder,int inbegin,int inend,int key){
for(int i = inbegin;i<inend;i++){
if(inorder[i] == key){
//找到了返回下标
return i;
}
}
return -1;
}
}
但是这样代码就没有问题了吗，肯定是有的，你看，当你的preIndex局部变量递归回去的时候，因为你当前的preIndex是局部变量，递归回来后preIndex并没有保留之前的下标值，重新回到了0
还有，当前递归的结束条件是什么，你看此时假如你递归到后面，比如我画图的这样
因此我们要当ib<=ie的时候还才继续递归，否则终止递归
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTreeChild(preorder,inorder,0,inorder.length-1);
}
int preIndex = 0;//改动一：添加类成员变量表示preIndex
public TreeNode buildTreeChild(int [] preorder,int [] inorder,int inbegin,int inend){
//改动二：添加递归终止条件
if(inbegin > inend){
return null;
}
//每次递归的时候创建一个根节点
TreeNode root = new TreeNode(preorder[preIndex]);
//寻找根节点下标，每一次递归preIndex都要往后走，寻找下一个根节点下标
int rootIndex = findRootIndex(inorder,inbegin,inend,preorder[preIndex]);
preIndex++;
//递归当前根节点的左子树
root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);
//最后返回当前的根节点
return root;
}
//在数组区间内寻找每次一指定根节点key
private int findRootIndex(int [] inorder,int inbegin,int inend,int key){
for(int i = inbegin;i<=inend;i++){
if(inorder[i] == key){
//找到了返回下标
return i;
}
}
return -1;
}
}
12. 根据中序与后序遍历创建二叉树
题目链接
这一题跟刚刚那一题思想差不多，只不过不是从前往后遍历了，是从后往前遍历而已，然后节点是创建根节点后先创建右子树再创建左子树
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
postIndex = postorder.length-1;//改动二：从后续遍历数组的最后一个开始往前遍历
return buildTreeChild(postorder,inorder,0,inorder.length-1);//改动一
}
int postIndex = 0;//改动三：修改变量
public TreeNode buildTreeChild(int [] preorder,int [] inorder,int inbegin,int inend){
if(inbegin > inend){
return null;
}
//每次递归的时候创建一个根节点
TreeNode root = new TreeNode(preorder[postIndex]);
//寻找根节点下标，每一次递归postIndex都要往前走，寻找下一个根节点下标
int rootIndex = findRootIndex(inorder,inbegin,inend,preorder[postIndex]);
postIndex--;//改动四：每次postIndex往前走
//递归当前根节点的左子树
//根据后序遍历，先创建右子树再创建左子树
root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);
root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
//最后返回当前的根节点
return root;
}
//在数组区间内寻找每次一指定根节点key
private int findRootIndex(int [] inorder,int inbegin,int inend,int key){
for(int i = inbegin;i<=inend;i++){
if(inorder[i] == key){
//找到了返回下标
return i;
}
}
return -1;
}
}
13. 根据二叉树创建对应字符串
题目链接
因为题目中的是前序遍历，这一题核心就是如果左子树不为空，右子树为空，那就没必要递归右边了，直接返回就好，右边空的不用加上()表示空子树
如果左子树和右子树都是空，也是直接返回就好了，也不用加上()表示空子树
但是，如果左边是空的，右边不是，那左边就要加上()表示空子树
递归左树前加上(，递归完右树封上)
public String tree2str(TreeNode root) {
StringBuilder stringBuilder = new StringBuilder();
if(root == null){
return stringBuilder.toString();
}
tree2strChild(root,stringBuilder);
return stringBuilder.toString();
}
public void tree2strChild(TreeNode t,StringBuilder stringBuilder){
//遇到空节点直接返回，开始递归其他节点
if(t == null){
return;
}
stringBuilder.append(t.val);//放入最开始根节点
if(t.left != null){
//开始递归左子树，加上左括号
stringBuilder.append("(");
tree2strChild(t.left,stringBuilder);
//左边递归完了封上右括号
stringBuilder.append(")");
}else{
//说明左边是空的，此时再判断右边是不是空的
if(t.right == null){
//是空的直接返回，不用加括号了
return;
}else{
//如果右边不空，左边就要加上括号表示空节点
stringBuilder.append("()");
}
}
//此时左边节点确定是空的了
if(t.right != null){
//开始递归右树，左括号表示开始
stringBuilder.append("(");
tree2strChild(t.right,stringBuilder);
//右子树递归完，封上右括号
stringBuilder.append(")");
}else{
//说明右节点也是空的，直接返回就好了
return;
}
}
14. 非递归打印前中后序
之前我们都是使用递归去打印三种顺序，这次我们使用非递归方式完成
非递归打印前序
非递归打印中序
非递归打印后序
我们会使用到栈和中间元素top去保存信息
我们先来讲讲前序
因为不是递归，因此我们要使用一个中间变量current去代替root根节点行动
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
if(root == null){
return;
}
TreeNode current = root;
//遍历左树节点
while(cur != null){
System.out.println(cur.val+" ");
stack.push(cur);
cur = cur.left;
}
//结束后开始弹出
TreeNode top = stack.pop();
//遍历当前根节点右子树
cur = cur.right;
}
}
但是当前代码就不存在问题了吗，并不是，你想
还有，如果D右子树还有元素，你要放入栈继续遍历，但是你的入栈操作是在上面循环中，放不了，你说我在写个循环，这不就写不完了吗
解决以上问题很简单，外边再套一层循环就好了，如果最外层循环都进不来，比如此时D节点左子树是空的，那我们就要去D右子树，因此我们把最外层循环再加上栈不为空的条件while(cur != null || !stack.Emprty()就好了，此时就算最外层循环中current为空，我的循环还是可以进来的（因为此时栈还有元素）
此时内部循环进不来，此时弹出栈顶元素给top，此时B的右子树就不会被遗忘了
我们再来讲讲中序遍历
其实也差不多，只不过是打印的时机不一样而已
因此代码只需要改动几个地方
public Stack<TreeNode> inorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
if(root == null){
return null;
}
TreeNode current = root;
//遍历左树节点
while(current != null || !stack.empty()){
while(current != null){
//改动一：删除此时打印
//System.out.print(current.value+" ");
stack.push(current);
current = current.left;
}
//结束后开始弹出
TreeNode top = stack.pop();
//改动二：添加弹出时打印的代码
System.out.print(top.value+" ");
//遍历当前根节点右子树
current = top.right;
}
return stack;
}
后序遍历有点特殊
当然前面还是和中序和前序遍历的逻辑与，那我们着重分析特殊情况
//非递归打印后序序列
public Stack<TreeNode> postorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
if(root == null){
return null;
}
TreeNode current = root;
while(current != null || !stack.empty()){
while(current != null){
stack.push(current);
current = current.left;
}
}
//给个变量top查看栈顶元素，如果右子树是空的就正常弹出
TreeNode top = stack.peek();
if(top.right == null){
System.out.println((top.value));
stack.pop();
}else{
//如果右子树不为空也要遍历
current = top.right;
}
return stack;
}
此时代码就没问题…了…吗？有问题，什么问题呢？重复打印问题
我们只需要在TreeNode current = root;下边一样定义TreeNode preV = null;，在current = top.right;前加上preV = top，在if(root.right == null){加上条件top.right == preV就可以了
//非递归打印后序序列
public Stack<TreeNode> postorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
if(root == null){
return null;
}
TreeNode current = root;
TreeNode preV = null;//改动一
while(current != null || !stack.empty()) {
while (current != null) {
stack.push(current);
current = current.left;
}
//给个变量top查看栈顶元素，如果右子树是空的就正常弹出
TreeNode top = stack.peek();
if (top.right == null || top.right == preV) {//改动三
System.out.println((top.value));
stack.pop();
} else {
preV = top;//改动二
//如果右子树不为空也要遍历
current = top.right;
}
}
return stack;
}
这里的preV起什么作用呢，你看，一旦我访问过右子树，那我就把右子树节点的值存入preV中，等我下一次遍历去检查preV有没有值，如果当前top节点中的值等于我preV中的值，说明我右子树遍历过，就没有必要再遍历了，直接继续弹出就好了，非常巧妙
原文地址：https://blog.csdn.net/Pluchon/article/details/149692275
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！