专栏简介 :java语法及数据结构

题目来源:leetcode,牛客,剑指offer

创作目标:从java语法角度实现底层相关数据结构,达到手撕各类题目的水平.

希望在提升自己的同时,帮助他人,,与大家一起共同进步,互相成长.

学历代表过去,能力代表现在,学习能力代表未来!

目录

前言

一>树形结构

1.树的概念

2.树的应用

二>二叉树

1.二叉树的概念

2.两种特殊的二叉树

3.二叉树的性质

4.二叉树的存储

5.二叉树的创建

6.二叉树的遍历

1)前序遍历

2)中序遍历

3)后序遍历

4)层序遍历

5)子问题思路与遍历思路的区别

6)leetcode提交做法

三 >二叉树常见面试题

1.选择题部分:

2.编程题部分:

1.节点个数

2.叶子节点个数

3.获取二叉树第K层节点的个数

4.二叉树的高度

5.检测值为value的元素是否存在

6.判断一棵树是不是完全二叉树(栈)

7.相同的树

8.另一棵树的子树

9.平衡二叉树(字节跳动原题)

10.对称二叉树

11.创建二叉树

12.二叉树的最近公共祖先

13.二插搜索树转双向链表

14.从前序遍历到中序遍历构造二叉树

15.从中序遍历到后序遍历构造二叉树

16.根据二叉树创建字符串

17.前序遍历非递归写法

18.中序遍历非递归写法

19.后序遍历非递归写法

总结>

前言

本文主要讲解二叉树重点知识很少涉及无关的背景知识,旨在即快速又清晰熟练掌握二叉树并手撕相关面试题,希望我的文章能对你有所帮助与启发.

一>树形结构

1.树的概念

学习二叉树之前我们首先要了解树形结构,树是一种非线性结构,它是由n(n>=0)个有限节点组成的的具有层次关系的集合,之所以把它叫做树,是因为该结构看起来像是一颗倒挂的树.树具有以下特点:

树的根节点无前驱节点
其余节点有且仅有一个前驱,但有多个后继
树是由递归定义的

重要概念:

节点的度:一个节点含有的子节点的个数叫做节点的度,如上图中A的度为7.
树的度:一个树中,最大节点的度称为树的度,如上图数的度为7.
叶子节点:度数为0的节点叫叶子节点
父节点:若一个节点有子节点,则这个节点称为其子节点的父节点.
根节点:一个树种,无父节点的节点.如A
节点的层次:从根开始定义,根为第一层,根的子节点为第二层,以此类推.
树的深度:树的最大层次.如上图树的深度为3.

2.树的应用

我们平时使用的各种文件系统管理,其底层逻辑都是树形结构.

二>二叉树

1.二叉树的概念

在树形结构的基础上二叉树有两个特点:

每个节点最多两颗子树,即二叉树不存在度数大于二的节点.
每个二叉树的子树有左右之分,其子树的次序不能颠倒,因此二叉树是有序树.

2.两种特殊的二叉树

满二叉树:每一层的节点数都达到最大值就是满二叉树.
完全二叉树:完全二叉树是效率很高的数据结构,每一个节点与树中编号一一对应,所以满二叉树是一种特殊的完全二叉树.

3.二叉树的性质

若规定根节点的层数为1,则一颗非空二叉树的第i层有有 $2^{i-1}$ (i>0)个节点.
若规定根节点的二叉树的深度为1,则深度为k的二叉树的最大节点个数为 $2^{k-1}$ (k>=0).
对于高度为k的二叉树,最多有 $2^{k+1}-1$ 个节点.
对任何一颗二叉树,如果其叶子节点个数为n0,其度数为2的非叶子节点的个数为n2,那么 n0=n2+1.证法如下(1)
具有n个节点的完全二叉树的深度为 $\log_{2} (n+1)$ 向上取整.证法如下(2)
对于有n个节点的完全二叉树,如果按照从上到下从左到右的顺序对所以有节点从0开始编号,则对于序号为i的节点有:
若i>0双亲序号为:(i/2)-1.
若2i+1<n,左孩子序列为2i+1,否则无左孩子.
若2i+2<n,右孩子序列为2i+2,否则无右孩子.

证(1):>

设二叉树顶点数=N,度数为0的节点为n0,度数为1的节点为n1,度数为2的为n2.
度数和=顶点数(N)-1.(度数和 = N-1)
顶点数(N) = n0+n1+n2.
度数和 = 0*n0+1*n1+2*n2.
结合2,3,4可得:0*n0+1*n1+2*n2 = n0+n1+n2-1
化简得:n0 = n2+1
证(2):>

深度为1的节点数 $2^{0}$ ,深度为2的节点数为 $2^{1}$ .....深度为k的节点数为 $2^{k-1}$ ,由等比数列求和公式: ${\color{Red} \frac{1-2^{n}}{1-2}$ .那么节点数为n的深度为 ${\color{Magenta} \log_{2}n+1}$ .

4.二叉树的存储

二叉树的存储结构分为顺序存储和类似于链表的链式存储,本章采用链式存储.表示方法采用孩子表示法,即一个节点中包含数据域,左孩子与右孩子.

class Node {
int val; // 数据域
Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
}

5.二叉树的创建

二叉树的创建需要三步:

创建结点:包含数值域,左孩子结点,右孩子结点
创建二叉树:我们采用前序遍历+递归的方式创建二叉树.
输入要创建的序列:本文二叉树的物理连接方式是链表,所以我们采用LinkedList集合存储二叉树内容.使用asList方法写入数组.

class TreeNode{//二叉树节点int data;TreeNode1 leftChild;TreeNode1 rightChild;public TreeNode1(int data) {this.data = data;}
}
public static TreeNode createBinaryTree(LinkedList<Integer> inputList){//创建二叉树TreeNode node = null;if (inputList==null||inputList.isEmpty()){return null;}Integer data = inputList.removeFirst();//每次取出集合中的第一个元素//这里判空很重要,如果元素为空,则不在进一步递归.if (data!=null){node = new TreeNode1(data);node.leftChild = createBinaryTree(inputList);node.rightChild = createBinaryTree(inputList);}return node;}
public static void main(String[] args) {LinkedList<Integer> inputList = new LinkedList<>        (Arrays.asList(3,2,9,null,null,10,null,null,8,null,4));TreeNode1 treeNode1 = createBinaryTree(inputList);}

6.二叉树的遍历

初学二叉树时,许多同学会很疑惑二叉树为什么需要这么多的遍历方法?

1)前序遍历

public static void preOrderTraveral(TreeNode node){//to前序遍历if (node==null){return;}System.out.print(node.data+" ");preOrderTraveral(node.leftChild);preOrderTraveral(node.rightChild);}

2)中序遍历

public static void midOrderTraveral(TreeNode node){//中序遍历if (node==null){return;}midOrderTraveral(node.leftChild);System.out.print(node.data+" ");midOrderTraveral(node.rightChild);}

3)后序遍历

public static void lastOrderTraveral(TreeNode node){//后序遍历if (node==null){return;}lastOrderTraveral(node.leftChild);lastOrderTraveral(node.rightChild);System.out.print(node.data+" ");}

4)层序遍历

  public static void levelOrderTraveral(TreeNode root) {//层序遍历Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()){TreeNode node = queue.poll();System.out.println(node.data);if (node.leftChild!=null){queue.offer(node.leftChild);}if (node.rightChild!=null){queue.offer((node.rightChild));}}}

5)子问题思路与遍历思路的区别

许多初学二叉树的同学,可能无法很好的理解子问题思路与遍历思路的区别,导致许多题目一知半解.下面我们详细讲解一下子问题思路与遍历思路.假设我们要求一颗二叉树所有节点的个数.

遍历思路:定义一个变量count记录节点个数,每遍历一个节点count++,最后返回count即可.
子问题思路:将二叉树看成由许多个小的二插树组成.每个小树算完再返回给上一层的大树.

class Solution {//遍历思路int count = 0;public int countNodes(TreeNode root) {if(root==null){return 0;}count++;countNodes(root.left);countNodes(root.right);return count;}
}

class Solution {//子问题思路拆解写法public int countNodes(TreeNode root) {if(root==null){return 0;}int leftTreeCount = countNodes(root.left);int rightTreeCount = countNodes(root.right);return leftTreeCount+rightTreeCount+1;}
}

6)leetcode提交做法

在leetcode中刷题我们发现,无论是哪种遍历方式都需要返回一个List集合类型的值,也就是将二叉树的信息存在集合中并返回.这里提供两种思路:

遍历思路:如果在二叉树的类中new一个List对象,那么每次遍历都会new对象,很显然这样做无法返回所有对象,所以我们只需将List集合创建在前序遍历类外,不断的遍历二叉树向集合中添加元素,最后返回存好的对象即可.
子问题思路:如果每次遍历二叉树都会创建新的对象,那么我们可以把所有创建出的对象,分为左右子树,最终加和到一个对象里返回即可.

    List<Integer> relist = new ArrayList<Integer>();//集合创建在类外public List<Integer> preorderTraversal(TreeNode root) {//遍历思路if(root==null){return relist;}relist.add(root.val);preorderTraversal(root.left);preorderTraversal(root.right);return relist;}

public List<Integer> preorderTraversal(TreeNode root) {//子问题思路List<Integer> relist = new ArrayList<Integer>();if(root==null){return relist;}relist.add(root.val);List<Integer> leftTree = preorderTraversal(root.left);relist.addAll(leftTree);//所有的左树List<Integer> rigthTree = preorderTraversal(root.right);relist.addAll(rigthTree);//所有的右树return relist;}

leetcode中层序遍历的提交方法更为特殊,需要返回一个List集合的二维数组.只需每遍历一层二叉树就存进一个一维数组中,最后将所有一位数组存进二维数组中返回即可.

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()){int size = queue.size();List<Integer> list = new ArrayList<>();while(size!=0){TreeNode cur = queue.poll();if(cur.left!=null){queue.offer(cur.left);}if(cur.right!=null){queue.offer(cur.right);}size--;list.add(cur.val);}ret.add(list);}return ret;}

三 >二叉树常见面试题

1.选择题部分:

1.1 某二叉树公有399个节点,其中有199个度为2的节点,则该二叉树中子节点的个数为().

A.200 B.198 C.199 D.不存在这样的二叉树

由上文已知,n0 = n2+1.那么199个2度节点就对应198个0度节点.(B)

1.2 在具有2n个节点的完全二叉树中,子节点个数为()

A.n B.n+1 C.n-1 D.n/2

2n个节点说明节点数一定是偶数, 那么该二叉树n1 = 1(只有一个一度点),根据定理可知n0 = n2+1.设子节点个数为x,那么2n = n0+1+n2可写为:2n = 2x,化简得:x = n. (A)

1.3 一个具有767个节点的完全二叉树,其叶子节点个数为多少()

A.383 B.384 C.385 D.386

由上文已知767个节点为奇数,那么一定没有1度的节点,根据定理 n0 = n2+1,设子节点个数为x,那么767 = n0+n2可写为:2x-1,化简得x = 384. (B)

1.4 一颗完全二叉树的节点个数为531,那么这棵树的高度为()

A.11 B.10 C.8 D.12

由定理具有n个节点的完全二叉树深度为: $\log_{2} (n+1)$ 向上取整,所以我们需要估算 $\log_{2}532$ ,答案比9大但比10小,基于向上取整的原则我们选择10. (B)

1.5 二叉树的前序遍历和中序遍历如下:前序遍历:EFHIGJK;中序遍历:HFIEJKG,则二叉树的根节点为()

A.E B.F C.G D.H

前序遍历确定根节点为E,中序遍历确定二叉树的分布为:左树HFI,右树:JKG.(E)

1.6 设一颗二叉树的中序遍历序列:badce,后序遍历:bdeca,则二叉树前序遍历序列为()

A.adbce B.decab C.debac D.abcde

后续遍历确定二叉树的根节点位a,中序遍历确定二叉树的分布为:左树b,右树为dce.由后续遍历的规则画好二叉树后得前序遍历为abcde.

1.7 某二叉的后序遍历和中序遍历序列相同,均为ABCDEF,则按层序输出的序列为()

A.FEDCBA B.CBAFED C.DEFCBA D.ABCDEF

后续遍历确定根节点为F,中序遍历确定节点全部在左树,根据后续遍历的规则画出图:

按层序输出为FEDCBA. (A)

2.编程题部分:

1.节点个数

此题变相考察二叉树的遍历方式,只要会遍历二叉树即可得出结果.博主提供两种思路:遍历思路和子问题思路.上文已对子问题思路和遍历思路详细的解析这里不过多赘述.

class Solution {//子问题思路public int countNodes(TreeNode root) {if(root==null){return 0;}return countNodes(root.left)+countNodes(root.right)+1;}
}
class Solution {//子问题思路拆解写法public int countNodes(TreeNode root) {if(root==null){return 0;}int leftTreeCount = countNodes(root.left);int rightTreeCount = countNodes(root.right);return leftTreeCount+rightTreeCount+1;}
}

class Solution {//遍历思路int count = 0;public int countNodes(TreeNode root) {if(root==null){return 0;}count++;countNodes(root.left);countNodes(root.right);return count;}
}

2.叶子节点个数

与节点个数写法一致,只不过记录数据的条件改为:当左右节点都为空时++.依旧是两种思路:

public static int getLeafNodeCount(TreeNode root){//完全二叉树叶子节点个数 遍历思路if (root==null){return 0;}if (root.leftChild==null&&root.rightChild==null){count++;}getLeafNodeCount(root.leftChild);getLeafNodeCount(root.rightChild);return count;}

 public static int getLeafNodeCount1(TreeNode root){//完全二叉树叶子节点个数 子问题思路if (root==null){return 0;}if (root.leftChild==null&&root.rightChild==null){return 1;}return getLeafNodeCount(root.leftChild)+getLeafNodeCount(root.rightChild);}

3.获取二叉树第K层节点的个数

该题使用子问题思路,重点是如何找到第K层?我们可以逆向来思考,如果让我们找第三层,我们可以假设第一层为3,每下一层就减1,当k==1时找到第三层.

public static int getLevelNodeCount(TreeNode root,int k){//获取第k层节点的个数if(root==null||k<=0){return 0;}if (k==1){return 1;}return getLevelNodeCount(root.leftChild,k-1)+getLevelNodeCount(root.rightChild,k-1);}

4.二叉树的高度

该题使用子问题思路,由于可能出现左树或右树为空另一颗树不为空的情况,所以我们可以比较左树和右树的高度,返回最大的即可.

public static int getHeight(TreeNode root){//获取二叉树的高度if (root==null){return 0;}int leftHeight = getHeight(root.leftChild);int rightHeight = getHeight(root.rightChild);return leftHeight>rightHeight?leftHeight+1:rightHeight+1;}

5.检测值为value的元素是否存在

该题为遍历思路,设置好递归的结束条件:节点为空或者节点的值为要查找的值.

public static TreeNode find(TreeNode root,char val){//检测value元素是否存在if (root==null){return null;}if (root.data==val){return root;}TreeNode retLeft = find(root.leftChild,val);//先去左树找if (retLeft!=null){//说明找到了return retLeft;}TreeNode retRight = find(root.rightChild,val);//再去右树找if (retRight!=null){//说明找到了return retRight;}return null;}

6.判断一棵树是不是完全二叉树(栈)

由之前的知识可知,完全二叉树每一个节点都与树中编号对应,说明一定是有顺序的.说到顺序我们首先要考虑栈和队列这两种数据结构.判断是不是完全二叉树,当一个节点没有利用价值时要立刻弹出,所以队列头进头出的方式最为合适.如下图所示,如果是完全二叉树那么队列中的空元素一定是连续的.

 public static boolean isCompleteTree1(TreeNode root){//判断是不是完全二叉树,队列if (root==null)return true;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()){TreeNode cur = queue.poll();if (cur!=null){queue.offer(cur.leftChild);queue.offer(cur.rightChild);}else {break;}}while (!queue.isEmpty()){if (queue.poll()!=null){return false;}}return true;}

7.相同的树

该题为子问题思路,做法为排除所有错误情况,剩余正确的.相同的树指的是,节点的值相同且树的结构也是相同的.

时间复杂度O(min(m,n)){左树节点个数为m,右树节点个数为n}

public boolean isSameTree(TreeNode p, TreeNode q) {if(p==null&&q!=null)return false;if(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,q.right);}

8.另一棵树的子树

该题建立在判断两颗树是否相同的基础上,运用子问题思路,先判断根节点是不是子树,如果没有再判断左子树中有没有子树,如果没有再判断右子树中有没有子树.

时间复杂度O(m*n)

本质判断相同

public boolean isSameTree(TreeNode p, TreeNode q) {if(p==null&&q!=null)return false;if(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,q.right);}public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(root==null||subRoot==null){return false;}//判断是否是相同的树if(isSameTree(root,subRoot)){return true;}//判断是不是左子树if(isSubtree(root.left,subRoot)){return true;}//判读是否是右子树if(isSubtree(root.right,subRoot)){return true;}//既不是左子树,也不是右子树,且不相同return false;}

9.平衡二叉树(字节跳动原题)

该题为子问题思路,需要之前判断二叉树高度的知识,一棵树如果是平衡二叉树那么其子树也一定是平衡二叉树,本质就是判断所有子树的高度差是否大于1.由于该题较为经典,所以提供两种做法不同的做法.

时间复杂度O(N^2)

遍历每一个子树,如果高度差<=1,返回true.但是该方法要为每一个节点都计算高度,时间复杂度大大增加.

public int height (TreeNode root){if(root==null){return 0;}int leftHeight = height(root.left);int rightHeight = height(root.right);return leftHeight>rightHeight?(leftHeight+1):(rightHeight+1);}public boolean isBalanced(TreeNode root) {if(root==null){return true;}int leftHeight = height(root.left);int rightHeight = height(root.right);return Math.abs(leftHeight-rightHeight)<=1&&isBalanced(root.left)&&isBalanced(root.right);}

时间复杂度O(N)

改进方法是如果父亲节点已经计算过高度那么子节点无需再次遍历.如果左右子树的高度差>1说明不是平衡二叉树,那么将不断递归返回-1.如果是平衡二叉树那么一定会返回一个正数,所以我们只需判断返回值的正负即可.

public int height (TreeNode root){if(root==null){return 0;}int leftHeight = height(root.left);int rightHeight = height(root.right);if(leftHeight>=0&&rightHeight>=0&&Math.abs(leftHeight-rightHeight)<=1){return leftHeight>rightHeight?(leftHeight+1):(rightHeight+1);}else{return -1;}}public boolean isBalanced(TreeNode root) {if(root==null){return true;}return height(root)>=0;}

10.对称二叉树

该题为子问题思路,对称二叉树要求左右子树对称的部分值相同,很明显一个参数的函数无法同时比较两颗子树,所以我们需要构造一个两个参数的函数,分别比较左树的左与右树的右.

public boolean isSymmetricChild(TreeNode rootleft,TreeNode rootrigth){if(rootleft==null&&rootrigth!=null){return false;}if(rootleft!=null&&rootrigth==null){return false;}if(rootleft==null&&rootrigth==null){return true;}if(rootleft.val!=rootrigth.val){return false;}return isSymmetricChild(rootleft.left,rootrigth.right)&&isSymmetricChild(rootleft.right,rootrigth.left);}public boolean isSymmetric(TreeNode root) {if(root==null){return true;}return isSymmetricChild(root.left,root.right);}

11.创建二叉树

该题主要分为三部分:创建结点,创建二叉树,中序遍历输出.创建结点与中序遍历上文已经提到过,创建二叉树时采用前序遍历的思想也可以很容易写出.

import java.util.*;class TreeNode{//创建结点public char val;public TreeNode left;public TreeNode right;public TreeNode(char val){this.val = val;}
}
public class Main{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);}public static void main(String[] args){Scanner in = new Scanner(System.in);while(in.hasNextLine()){String str = in.nextLine();TreeNode root = createTree(str);inorder(root);}}
}

12.二叉树的最近公共祖先

该题为子问题思路,先写明结束条件:节点等于空返回空节点,节点为根节点直接返回节点.然后去遍历左树与右树,判断返回值的三种情况:

节点分布在左右树两侧,即返回值都不为空,那么公共祖先一定是根节点.
节点分布在右侧,即返回值为第一个遇到的节点,那么公共祖先为第一个遇到的节点.
节点分布在右侧同理.

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root==null) return null;if(root==p||root==q){return root;}TreeNode leftT = lowestCommonAncestor(root.left,p,q);TreeNode rightT = lowestCommonAncestor(root.right,p,q);if(leftT!=null&&rightT!=null){return root;}else if(leftT!=null){return leftT;}else{return rightT;}}

假设这颗二叉树使用孩子双亲表示法:那么该问题就可以转化为双向链表求焦点,先让较长的链表走长度的差值步,两个链表长度相同时一边向前走一边判断值是否相同,值相同的节点即为公共祖先.但该题使用的是孩子表示法,无法得知上一个节点是谁,所以只能将节点的路径保存下来,而路径又是有序的,提到顺序我们想到栈和队列,我们需要从后向前找公共节点,很明显需要用栈来保存,而一个栈只能保存一个节点的路径,所以我们需要两个栈.保存好如图所示的路径后,让栈内元素多的先pop(),直到两个栈元素个数相同,然后两个栈一边出元素一边比较元素,遇到相同的就是公共节点.现在最关键的问题就是如何在栈内保存指定的路径?我们可以构造一个储存路径的函数,比较目标节点node和根节点root的关系不断更新路径.栈内路径保存完毕后,就是出栈操作相对简单,这里不过多赘述.

public boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode>stack){if(root==null||node==null){return false;}stack.push(root);if(root==node){return true;}boolean flg = getPath(root.left,node,stack);if(flg==true){return true;}flg = getPath(root.right,node,stack);if(flg==true){return true;}stack.pop();return false;}public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root==null) return null;Stack<TreeNode> stack1 = new Stack<>();getPath(root,p,stack1);Stack<TreeNode> stack2 = new Stack<>();getPath(root,q,stack2);int size1 = stack1.size();int size2 = stack2.size();if(size1>size2){int size = size1-size2;while(size!=0){stack1.pop();size--;}while(!stack1.isEmpty()&&!stack2.isEmpty()){if(stack1.peek()==stack2.peek()){return stack1.pop();}else{stack1.pop();stack2.pop();}}}else{int size = size2-size1;while(size!=0){stack2.pop();size--;}while(!stack1.isEmpty()&&!stack2.isEmpty()){if(stack1.peek()==stack2.peek()){return stack2.pop();}else{stack1.pop();stack2.pop();}}}return null;}

13.二插搜索树转双向链表

该题为遍历思路,难点在于如何在中序遍历的过程中修改指向,首先我们确定递归的结束条件为节点为空,当节点为null时说明我们此时找到了中序遍历的第一个节点(4),此时我们可以修改节点的指向让它的left指向null,再去遍历左树左树也为null,返回到节点(6),此时应该让(6)的左指向(4),再让(4)的右指向(6),但我们已经找不到(4)这个节点了,所以为了记录节点可以在函数外定义成员遍历prev记录node的值,但在第一个节点时不需要这一步操作,因为prev初始值为null,prev.right会出现空指针异常.

TreeNode prev = null;public void inOrder(TreeNode node){if(node==null) return;inOrder(node.left);//打印node.left = prev;if(prev!=null){prev.right = node;}prev = node;inOrder(node.right);}public TreeNode Convert(TreeNode pRootOfTree) {if(pRootOfTree==null) return null;inOrder(pRootOfTree);TreeNode head = pRootOfTree;while(head.left!=null){head = head.left;}return head;}

14.从前序遍历到中序遍历构造二叉树

该题为子问题思路,首先要明白的是前序遍历用来确定每一颗子树根节点,中序遍历用来确定二叉树的构造情况并创建二叉树,

int preIndex = 0;public TreeNode creativePbyI(int[] preorder, int[] inorder,int beging,int end){if(beging>end){return null;}TreeNode root = new TreeNode(preorder[preIndex]);int rootIndex = findIndex(inorder,beging,end,preorder[preIndex]);if(rootIndex==-1){return null;}preIndex++;root.left = creativePbyI(preorder,inorder,beging,rootIndex-1);root.right = creativePbyI(preorder,inorder,rootIndex+1,end);return root;}public int findIndex( int[] inorder,int beging,int end,int key){for(int i = 0;i<=end;i++){if(inorder[i]==key){return i;}}return -1;}public TreeNode buildTree(int[] preorder, int[] inorder) {if(preorder==null||inorder==null){return null;}return creativePbyI(preorder,inorder,0,preorder.length-1);}

15.从中序遍历到后序遍历构造二叉树

做法与上一题类似,更改函数名即可.

int postIndex = 0;public TreeNode creativePbyI(int[] inorder, int[] postorder,int beging,int end){if(beging>end){return null;}TreeNode root = new TreeNode(postorder[postIndex]);int rootIndex = findIndex(inorder,beging,end,postorder[postIndex]);if(rootIndex==-1){return null;}postIndex--;root.right = creativePbyI(inorder,postorder,rootIndex+1,end);root.left = creativePbyI(inorder,postorder,beging,rootIndex-1);return root;}public int findIndex( int[] inorder,int beging,int end,int key){for(int i = 0;i<=end;i++){if(inorder[i]==key){return i;}}return -1;}public TreeNode buildTree(int[] inorder, int[] postorder) {if(postorder==null||inorder==null){return null;}postIndex = postorder.length-1;return creativePbyI(inorder,postorder,0,inorder.length-1);}

16.根据二叉树创建字符串

本题考察了对二叉树递归的应用与字符串拼接相关的知识,按题意我们分析出可能出现的所有情况,由于是前序遍历,所以我们先从左树的情况来判断,先拼接一个元素当t.left!=null时加"(",并继续递归.当t.left=null&&t.right=null时直接retrun,回溯到上一步会再加一个")",当t.left=null&&t.right!=null加"()".如果左树遍历完我们再去遍历右树t,right!=null加"(",t.right=null时直接返回.

public void treeToString(TreeNode t,StringBuffer sb){if(t==null){return;}sb.append(t.val);if(t.left!=null){sb.append("(");treeToString(t.left,sb);sb.append(")");}else{//t.left==nullif(t.right==null){return;}else{sb.append("()");}}if(t.right!=null){sb.append("(");treeToString(t.right,sb);sb.append(")");}else{return;}}public String tree2str(TreeNode root) {if(root==null) return null;StringBuffer sb = new StringBuffer();treeToString(root,sb);return sb.toString();}

17.前序遍历非递归写法

牵扯到顺序就考虑栈和队列,前序遍历遍历完左树后需要回溯到右树继续遍历,所以必须保存它的路径,方便后续回溯,那么用栈最为合适.

public static void preOrderTraveralWithStack(TreeNode root){//非递归前序遍历Stack<TreeNode> stack = new Stack<TreeNode>();TreeNode node = root;while (node!=null||!stack.isEmpty()){while (node!=null){System.out.println(node.data);stack.push(node);node = node.leftChild;}if(!stack.isEmpty()){node = stack.pop();node = node.rightChild;}}}

18.中序遍历非递归写法

与前序遍历写法一致,不过更改打印元素位置,当中序遍历元素被弹出时打印.

 public List<Integer>inorderTraversal(TreeNode root) {List<Integer> ret = new ArrayList<>();if(root==null) return ret;Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while(cur!=null||!stack.isEmpty()){while(cur!=null){stack.push(cur);cur = cur.left;}if(!stack.isEmpty()){TreeNode top = stack.pop();ret.add(top.val);cur = top.right;}}return ret;}

19.后序遍历非递归写法

与中序遍历不同的是,后续遍历到cur.left=null时必须确保cur.right=null才能弹出cur.所以只能peek(）栈顶的元素看它的右树是否存在,不存在就弹出,存在还需遍历右树.但此时会出现一个为问题,右树的遍历会陷入死循环.所以需要对右树的遍历加限制条件,如果右树已经遍历或者右树为空,可以直接弹出.因此当右树遍历后就用prev来记录top节点,如果prev=top说明已经遍历过,直接弹出即可.

public List<Integer> postorderTraversal(TreeNode root) {List<Integer> ret = new ArrayList<>();if(root==null) return ret;Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;TreeNode prev = null;while(cur!=null||!stack.isEmpty()){while(cur!=null){stack.push(cur);cur = cur.left;}TreeNode top = stack.peek();if(top.right==null||top.right==prev){stack.pop();ret.add(top.val);prev = top;//记录最近一次遍历二叉树}else{cur = top.right;}}return ret;}