系列文章目录
集合及数据结构第九节————树和二叉树
树和二叉树
- 树型结构的概念
- 树的概念
- 树的表示形式（了解）
- 树的应用
- 二叉树的概念
- 两种特殊的二叉树
- 二叉树的性质
- 二叉树的性质练习
- 二叉树的存储
- 二叉树的遍历
- 二叉树的基本操作
- 二叉树相关练习题
文章目录
- 系列文章目录
- 一、树型结构
- 二、二叉树（重点）（ * * * ）
一、树型结构
1.树型结构的概念
树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
- 有一个特殊的结点，称为根结点，根结点没有前驱结点
- 除根结点外，其余结点被分成M(M > 0)个互不相交的集合T1、T2、…、Tm，其中每一个集合Ti (1 <= i <=m) 又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。
- 树是递归定义的
一棵树是由若干个不相交的子树组成的。
注意：树形结构中，子树之间不能有交集，否则就不是树形结构
2.树的概念（ * * ）
结点的度：一个结点含有子树的个数称为该结点的度； 如上图：A的度为6
树的度：一棵树中，所有结点度的最大值称为树的度； 如上图：树的度为6
叶子结点或终端结点：度为0的结点称为叶结点； 如上图：B、C、H、I…等节点为叶结点
双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点； 如上图：A是B的父结点
孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点； 如上图：B是A的孩子结点
根结点：一棵树中，没有双亲结点的结点；如上图：A
结点的层次（深度）：从根开始定义起，根为第1层，根的子结点为第2层，以此类推
树的高度：树中结点的最大层次； 如上图：树的高度为4
树的以下概念只需了解，在看书时只要知道是什么意思即可：
非终端结点或分支结点：度不为0的结点； 如上图：D、E、F、G…等节点为分支结点
兄弟结点：具有相同父结点的结点互称为兄弟结点； 如上图：B、C是兄弟结点
堂兄弟结点：双亲在同一层的结点互为堂兄弟；如上图：H、I互为兄弟结点
结点的祖先：从根到该结点所经分支上的所有结点；如上图：A是所有结点的祖先
子孙：以某结点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是A的子孙
森林：由m（m>=0）棵互不相交的树组成的集合称为森林
3.树的表示形式（了解）
树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，如：双亲表示法，孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子兄弟表示法。
lass Node {
int value; // 树中存储的数据
Node firstChild; // 第一个孩子引用
Node nextBrother; // 下一个兄弟引用
}
4.树的应用
文件系统管理（目录和文件）
二、二叉树（重点）（ * * * ）
1.二叉树的概念
一棵二叉树是结点的一个有限集合，该集合：
- 或者为空
- 或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
从上图可以看出： - 二叉树不存在度大于2的结点
- 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
注意：对于任意的二叉树都是由以下几种情况复合而成的：
大自然的二叉树：
2.两种特殊的二叉树（ * * * ）
- 满二叉树: 一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵二叉树的层数为K，且结点总数是 2^k -1，则它就是满二叉树。
- 完全二叉树: 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
3.二叉树的性质（ * * ）
- 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有 2 ^ (i - 1) (i>0)个结点
- 若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是2 ^ k - 1 (k>=0)
- 对任何一棵二叉树, 如果其叶结点个数为 n1, 度为2的非叶结点个数为 n2,则有n1＝n2＋1
- 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i的结点有：
- 若i > 0，双亲序号：(i - 1) / 2；i=0，i为根结点编号，无双亲结点
- 若2i + 1 < n，左孩子序号：2i + 1，否则无左孩子
- 若2i + 2 < n，右孩子序号：2i + 2，否则无右孩子
4.二叉树的性质练习
- 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ B ）
A 不存在这样的二叉树
B 200
C 198
D 199
解析：
对任何一棵二叉树, 如果其叶结点个数为 n1, 度为2的非叶结点个数为 n2,则有n1＝n2＋1
2.在具有 2n 个结点的完全二叉树中，叶子结点个数为（ A ）
A n
B n+1
C n-1
D n/2A
解析：
3.一个具有767个节点的完全二叉树，其叶子节点个数为（ B ）
A 383
B 384
C 385
D 386
4.一棵完全二叉树的节点数为531个，那么这棵树的高度为（ B ）
A 11
B 10
C 8
D 12
解析：
5.二叉树的存储（ * * * ）
二叉树的存储结构分为：顺序存储(堆)和类似于链表的链式存储
二叉树的链式存储是通过一个一个的节点引用起来的，常见的表示方式有二叉和三叉表示方式，具体如下:
// 孩子表示法
class Node {
int val; // 数据域
Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
}
// 孩子双亲表示法
class Node {
int val; // 数据域
Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
Node parent; // 当前节点的根节点
}
6.二叉树的遍历
1. 前中后序遍历
学习二叉树结构，最简单的方式就是遍历。所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题(比如：打印节点内容、节点内容加1)。 遍历是二叉树上最重要的操作之一，是二叉树上进行其它运算之基础
在遍历二叉树时，如果没有进行某种约定，每个人都按照自己的方式遍历，得出的结果就比较混乱，如果按照某种规则进行约定，则每个人对于同一棵树的遍历结果肯定是相同的。如果N代表根节点，L代表根节点的左子树，R代表根节点的右子树，则根据遍历根节点的先后次序有以下遍历方式：
-
NLR：前序遍历(Preorder Traversal 亦称先根遍历)——访问根结点—>根的左子树—>根的右子树。
-
LNR：中序遍历(Inorder Traversal)——根的左子树—>根节点—>根的右子树。
- LRN：后序遍历(Postorder Traversal)——根的左子树—>根的右子树—>根节点
2. 层序遍历
层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历
【练习】
-
根据以上二叉树的三种遍历方式，给出以下二叉树的前中后序遍历结果：
前序：A B D E H C F G
中序：D B H E A F C G
后序：D H E B F G C A -
某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为( A )
A: ABDHECFG
B: ABCDEFGH
C: HDBEAFCG
D: HDEBFGCA
- 二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK;中序遍历：HFIEJKG.则二叉树根结点为( A )
A: E
B: F
C: G
D: H
- 设一课二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为( D )
A: adbce
B: decab
C: debac
D: abcde
- 某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出(同一层从左到右)的序列为( A )
A: FEDCBA
B: CBAFED
C: DEFCBA
D: ABCDEF
7. 二叉树的基本操作
二叉树的创建
在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。
public TreeNode createTree(){//创建一棵二叉树，初创建成功后返回根节点
TreeNode A = new TreeNode('A');
TreeNode B = new TreeNode('B');
TreeNode C = new TreeNode('C');
TreeNode D = new TreeNode('D');
TreeNode E = new TreeNode('E');
TreeNode F = new TreeNode('F');
TreeNode G = new TreeNode('G');
TreeNode H = new TreeNode('H');
A.left = B;
A.right = C;
B.left = D;
B.right = E;
C.left = F;
C.right = G;
E.right = H;
return A;
}
注意：上述代码并不是创建二叉树的方式，真正创建二叉树方式后序详解重点介绍
前序遍历
void preOrder(TreeNode root){//前序遍历
// 前序遍历 根 -》 左子树 -> 右子树 (递归)
if(root == null) {//当树为空
return;
}
System.out.print(root.val+" ");//打印根
preOrder(root.left);//递归遍历树的左子树
preOrder(root.right);//左子树遍历完了，遍历右子树
}
中序遍历
void inOrder(TreeNode root){//中序遍历
//中序遍历:根的左子树--->根节点--->根的右子树
if(root == null) {//当树为空
return;
}
inOrder(root.left);//递归遍历树的左子树
System.out.print(root.val+" ");//打印根
inOrder(root.right);//左子树遍历完了，遍历右子树
}
后序遍历
void postOrder(TreeNode root){//后序遍历
//后序遍历(Postorder Traversal): 根的左子树--->根的右子树--->根节点
if(root == null) {//当树为空
return;
}
preOrder(root.left);//递归遍历树的左子树
preOrder(root.right);//左子树遍历完了，遍历右子树
System.out.print(root.val+" ");//打印根
}
8. 二叉树的基本操作
获取树中节点的个数
思路一：
- 利用递归的思想，遍历每一棵小树，若当前结点为空，返回0
- 每遇到一个节点计数器加1
int size(TreeNode root){// 获取树中节点的个数'
if (root == null){//树没有节点返回0
return 0;
}
//前序遍历
nodeSize++;
size(root.left);//递归遍历树的左子树
size(root.right);//左子树遍历完了，遍历右子树
return nodeSize;//返回最后统计的树的节点个数
}
思路二（子问题的思路）：
-
利用递归的思想，遍历每一棵小树，若当前结点为空，返回0
-
先获取左节点个数，再获取右节点个数
-
然后返回两者相加再加上根节点的个数1
-
然后两者相加
int size(TreeNode root){//获取树中节点的个数(子问题的思路解决)
if (root == null){//树没有节点返回0
return 0;
}
int leftSize = size(root.left);//递归遍历树的左子树
int rightSize = size(root.right);//左子树遍历完了，遍历右子树
return leftSize + rightSize + 1;//返回最后统计的树的节点个数
//return size(root.left) + size(root.right) + 1; //简化的写法
}
获取叶子节点的个数
思路一（遍历思路解决）：
- 利用递归的思想，遍历每一棵小树 判断是不是叶子是的话就计数器加1 。
public int leafSize;
int getLeafNodeCount(TreeNode root){ // 获取叶子节点的个数
if (root == null){//树没有节点返回0
return 0;
}
if(root.left == null && root.right == null){
leafSize++;
}
getLeafNodeCount(root.left);//递归遍历树的左子树
getLeafNodeCount(root.right);//左子树遍历完了，遍历右子树
return leafSize;
}
思路二（子问题的思路）：
-
利用递归的思想，遍历每一棵小树，若当前结点为空，返回0
-
当前节点的左右子树若都为空，说明该节点为叶子结点，返回1
-
先获取左节点个数，再获取右节点个数
int getLeafNodeCount(TreeNode root){ // 获取叶子节点的个数
if (root == null){//树没有节点返回0
return 0;
}
if(root.left == null && root.right == null){
return 1;
}
int leftLeafSize = getLeafNodeCount(root.left);//递归遍历树的左子树并统计左树叶子节点个数
int rightLeafSize = getLeafNodeCount(root.right);//左子树遍历完了，递归遍历树的右子树并统计右树叶子节点个数
return leftLeafSize + rightLeafSize;//返回左树叶子节点个数 + 右树叶子节点个数
//return getKLevelNodeCount(root.left) + getKLevelNodeCount(root.right);简化写法
}
获取第K层节点的个数
整棵树的第K层的节点数 = 左子树的第 k - 1层节点 + 右子树的 k - 1层节点
思路：
- 利用递归的思想，每进去一次，K-1，当k=1时，此时若该节点不为空则返回1
为空则返回0
-
先遍历左子树k层结点，再遍历右子树k层结点
-
最后左子树结点加上右子树结点，就是该层结点总数
int getKLevelNodeCount(TreeNode root,int k){// 获取第K层节点的个数
if (root == null){//树没有节点返回0
return 0;
}
if (k == 1){//第一层只有一个节点
return 1;
}
int leftLevelSize = getKLevelNodeCount(root.left,k-1);//递归遍历树的左子树的k - 1 层并统计左树 k- 1层的节点个数
int rightLevelSize = getKLevelNodeCount(root.right,k-1);//递归遍历树的右子树的k - 1 层并统计右树 k- 1层的节点个数
return leftLevelSize + rightLevelSize;//返回第K层节点的个数
//return getKLevelNodeCount(root.left,k -1) + getKLevelNodeCount(root.right,k - 1);//简化写法
}
获取二叉树的高度
整棵树的高度 = 左子树与右子树高度的最大值 + 1
思路：
-
分别统计左右子树的高度，然后进行比较
-
返回高度高的子树并加上根节点
代码实现
int getHeight(TreeNode root){// 获取二叉树的高度
if (root == null){//树没有节点返回0
return 0;
}
int leftHeight = getHeight(root.left);//递归遍历树的左子树并统计左子树的高度
int rightHeight = getHeight(root.right);//左子树遍历完了，递归遍历树的右子树并统计统计右子树的高度
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;//返回左子树与右子树高度的最大值 + 1（二叉树的高度）
//return getHeight(root.left) > getHeight(root.right) ? getHeight(root.left) + 1 : getHeight(root.right) + 1;//简化写法(但是重复递归操作了)
}
检测值为value的元素是否存在
-
利用递归的思想，先遍历左子树，若没有找到，则返回null
-
若返回不为null，则返回该结点
-
若左子树没有，则遍历右子树，道理相同
-
若最后都没找到，则返回null；
代码实现：
TreeNode find(TreeNode root, int val){ // 检测值为value的元素是否存在
if (root == null ){//树没有节点返回0
return null;
}
if(root.val == val){//判断根的val是不是要找的，如果是返回root
return root;
}
TreeNode ret1 = find(root.left,val);//递归遍历树的左子树并统计左子树的高度
if (ret1 != null){//在左边找到了
return ret1;
}
TreeNode ret2 = find(root.right,val);
if (ret2 != null){//在右边找到了
return ret2;
}
return null;
}
层序遍历
思路：
创建一个队列，用于储存每一层二叉树的结点，每一次将头元素进行出队后，又会将下一层的结点进行入队，然后依次进行遍历，直到队列为null则结束循环
先将根节点root进入到该队列，创建一个队列，每一个元素用于储存树的结点。
此后会在一个while循环里对该二叉树进行遍历，结束循环的条件为队列为空，
做法为：
- 每一次循环都会求一次队列的长度
- 创建一个队列进行储存该层结点
- 用while循环遍历队列
- 当队列不为空的时候，队首树的节点出队列并打印
- 把这个树的左子树和右子树按顺序存进队列
- 循环结束，树就以层序遍历的方式遍历完了。
void levelOrder(TreeNode root){//层序遍历
if(root == null) {//当树为空
return;
}
Queue<TreeNode> queue = new LinkedList<>();//创建一个队列
queue.offer(root);//将树放进队列
while (!queue.isEmpty()){//当队列不为空的时候，对二叉树进行遍历
TreeNode cur = queue.poll();//出队列，用cur来接收
System.out.print(cur.val + " ");//打印当前队列的队首的val（树从上到下，从左到右遍历的结果）
if (cur.left != null){//当树的左子树不为空时，把它放进队列
queue.offer(cur.left);
}
if (cur.right != null){//当树的右子树不为空时，把它放进队列
queue.offer(cur.right);
}
}
}
判断一棵树是不是完全二叉
思路：
创建一个队列，用于储存每一层二叉树的结点，每一次当将头元素进行出队后，我们又会将下一层的结点进行入队，然后依次进行遍历，直到队列为null时把null也入队后结束遍历。
当结束遍历后队列中只有null元素时这个树结束完全二叉树
否则就不是完全二叉树
boolean isCompleteTree(TreeNode root){// 判断一棵树是不是完全二叉树
if(root == null) {//当树为空，也是完全二叉树
return true;
}
Queue<TreeNode> queue = new LinkedList<>();//创建一个队列
queue.offer(root);//将树放进队列
while (!queue.isEmpty()){//当队列不为空的时候，对二叉树进行遍历
TreeNode cur = queue.poll();//出队列，用cur来接收
if (cur != null){
queue.offer(root.left);//当cur不为空时，把它的左子树放进队列
queue.offer(root.right);//当cur不为空时，把它的右子树放进队列
}else {
break;//结束这个循环
}
}
//需要判断队列中是否有非null的元素
while (!queue.isEmpty()){
//要一个元素一个元素判断是不是空
TreeNode tmp = queue.peek();
if (tmp == null){//是空
queue.poll();//出队列，来查看下一个元素是不是null
}else {//不是空
return false;//说明不是完全二叉树，返回false
}
}
return true;//循环结束，说明队列里的元素都是null，是完全二叉树，返回true
}
9. 二叉树相关练习题（ * * * ）
1. 检查两颗树是否相同
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1：
输入：p = [1,2,3], q = [1,2,3]
输出：true
示例 2：
输入：p = [1,2], q = [1,null,2]
输出：false
示例 3：
输入：p = [1,2,1], q = [1,1,2]
输出：false
思路·
对于结点的判断：
- 有一个结点为null，这时候直接返回false；
- 两个结点都为null，这时候直接返回true；
- 都不为空时进行值得判断，若不等返回false
整体来看，要判断两棵树是否相同，要先判断根，然后判断两棵树的左子树的值
是否相同，再判断两棵树的右子树的值是否相同。
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if ((p == null && q!= null) || (p != null && q == null) ){//有一个结点为null，这时候直接返回false(结构上不一样)
return false;
}
//上面得if语句走完后，要么两个都不是空，要么两个都是空
if (p == null && q == null){//两个结点都为null，这时候直接返回true
return true;
}
//两个都不是空
if (p.val != q.val){//q得val不等于q得val，返回false
return false;
}
//
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);//递归判断p，q的左子树和右子树
}
}
2. 另一棵树的子树
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
示例 1：
输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true
示例 2：
输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false
思路：
思路·
对于结点的判断：
- 有一个结点为null，这时候直接返回false；
- 两个结点都为null，这时候直接返回true；
- 都不为空时进行值得判断，若不等返回false
整体来看，要判断两棵树是否相同，要先判断根，然后判断两棵树的左子树的值
是否相同，再判断两棵树的右子树的值是否相同。
只需要传入相应的头节点与子树进行对比看看是否为同一棵树就好
只要存在就返回true
时间复杂度是O（n * m）每个节点都要判断是否相同
public boolean isSameTree(TreeNode p, TreeNode q) {
if ((p == null && q!= null) || (p != null && q == null) ){//有一个结点为null，这时候直接返回false(结构上不一样)
return false;
}
//上面得if语句走完后，要么两个都不是空，要么两个都是空
if (p == null && q == null){//两个结点都为null，这时候直接返回true
return true;
}
//两个都不是空
if (p.val != q.val){//q得val不等于q得val，返回false
return false;
}
//
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);//递归判断p，q的左子树和右子树
}
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null || subRoot == null){
return false;
}
//判断是不是和根节点相同
if (isSameTree(root,subRoot)){
return true;
}
//判断是不是和root的左子树相同
if (isSubtree(root.left,subRoot)){
return true;
}
//判断是不是和root的右子树相同
if (isSubtree(root.right,subRoot)){
return true;
}
//返回false
return false;
}
3. 翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
示例 2：
输入：root = [2,1,3]
输出：[2,3,1]
示例 3：
输入：root = []
输出：[]
思路：
利用递归的思想，把一个大树看成许多小树
只需要把每一个根节点的左子树和右子树进行交换就好
直到把所有的节点遍历完
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null){//当树为空，返回null
return null;
}
if (root.left == null && root.right == null){//递归到叶子节点，返回当前节点
return root;
}
//交换左右节点
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left);//遍历交换左树
invertTree(root.right);//遍历交换右树
return root;
}
}
4. 判断一颗二叉树是否是平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：true
示例 2：
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
示例 3：
输入：root = []
输出：true
思路一
具体做法类似于二叉树的前序遍历，即对于当前遍历到的节点，首先计算左右子树的高度，如果左右子树的高度差是否不超过 1，再分别递归地遍历左右子节点，并判断左子树和右子树是否平衡。
利用递归思想进行逐个遍历，但是这时候的时间复杂度较高，为O(N^2);
class Solution {
int getHeight(TreeNode root){// 获取二叉树的高度
if (root == null){//树没有节点返回0
return 0;
}
int leftHeight = getHeight(root.left);//递归遍历树的左子树并统计左子树的高度
int rightHeight = getHeight(root.right);//左子树遍历完了，递归遍历树的右子树并统计统计右子树的高度
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;//返回左子树与右子树高度的最大值 + 1（二叉树的高度）
//return getHeight(root.left) > getHeight(root.right) ? getHeight(root.left) + 1 : getHeight(root.right) + 1;//简化写法
}
public boolean isBalanced(TreeNode root) {
if (root == null ){//当树为空时，是平衡的，返回true
return true;
}
int leftHeight = getHeight(root.left);//递归遍历树的左子树并统计左子树的高度
int rightHeight = getHeight(root.right);//左子树遍历完了，递归遍历树的右子树并统计统计右子树的高度
//当|leftHeight - rightHeight |小于等于1 ，遍历判断左树是平衡的，遍历判断右树是平衡的，
// 这三个条件都成立时，返回true否则返回false
return Math.abs(leftHeight - rightHeight ) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
}
思路二（一边求高度，一边判断平衡）：
先递归地判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的，则返回其高度（高度一定是非负整数），否则返回 −1。如果存在一棵子树不平衡，则整个二叉树一定不平衡。
然后返回即可，此时的时间复杂度为O(N)
class Solution {
public boolean isBalanced(TreeNode root) {//时间复杂度是 O（N）（不需要判断每一个节点是否平衡）
if (root == null ){//当树为空时，是平衡的，返回true
return true;
}
return maxHeight(root) >= 0;//当getHeight的返回值大于等于0时，说明当前树时平衡的。
}
int maxHeight(TreeNode root){// 获取二叉树的高度
if (root == null){//树没有节点返回0
return 0;
}
int leftHeight = maxHeight(root.left);//递归遍历树的左子树并统计左子树的高度
if (leftHeight < 0){//左子树不平衡，直接返回-1
return -1;
}
int rightHeight = maxHeight(root.right);//左子树遍历完了，递归遍历树的右子树并统计统计右子树的高度
//判断当前节点左右子树都是平衡的时，返回真实的高度
if (leftHeight >= 0 && rightHeight >= 0 && Math.abs(leftHeight - rightHeight) <= 1){
return Math.max(leftHeight,rightHeight) + 1;//返回真实的高度
}else {
return -1;
}
}
}
5. 对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false
思路：
两个树在什么情况下对称，什么时候不对称：
- root的左子树和右子树一个为空一个不为空的情况下，一定不对称
- root的左子树和右子树都为空时是对称的
- root的左子树和右子树值不一样时，不对称
- root的左子树和右子树值一样时满足下面三个条件就是对称的
- 根的值一样
- 左树的左值和右树的右值一样
- 左树的右值和右树的左值一样
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null){
return true;
}
return isSymmetricChild(root.left,root.right);
}
private boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree){
if (leftTree == null && rightTree == null){//root的左子树和右子树都为空时是对称的
return true;
}
if ((leftTree == null || rightTree== null)){//root的左子树和右子树一个为空一个不为空的情况下，一定不对称
return false;
}
if (leftTree.val == rightTree.val){//根的值一样,判断左树的左值和右树的右值是否一样和左树的右值和右树的左值是否一样
return isSymmetricChild(leftTree.left,rightTree.right) && isSymmetricChild(leftTree.right,rightTree.left);
}
return false;根的值一样左树的左值和右树的右值不一样或者左树的右值和右树的左值不一样，返回false
}
}
6. 二叉树的构建及遍历
描述
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
输入描述：
输入包括1行字符串，长度不超过100。
输出描述：
可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。‘
示例1
输入：
ABC##DE#G##F###
输出：
c b e g d f a
思路：
依旧采用递归的思想
对字符串的每一个元素进行遍历，并进行判断
在遍历时，我们创建一个静态变量为size，此后每遍历一个元素，size就++
若不为’#‘，则该结点设为根节点
并且size++；
然后因为是前序遍历，所以根节点后面应该是左子树，然后是右子树
若为’#’，则该节点为null，只需要size++即可
最后返回该结点就好
import java.util.Scanner;
class TreeNode {//定义树的结点（孩子表示法）
public char val;
public TreeNode left;//左子树
public TreeNode right;//右子树
public TreeNode(char val) {
this.val = val;
}
}
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextLine()) {
String str = in.nextLine();
TreeNode root = createTree(str);//接收create创建的树的根节点
inorder(root);
}
}
public static int i = 0;//把 i 定义为当前类的成员变量)
public static TreeNode createTree(String str){//根据接收的字符串创建树
TreeNode root = null;
//1. 遍历字符串//每次递归i要改变(把 i 定义为当前类的成员变量)
if (str.charAt(i) != '#'){//当字符不是 # 时，创建树
//2. 根据前序遍历创建二叉树
root = new TreeNode(str.charAt(i));//当字符不是 # 时,把下标为i的字符设为根节点
i++;
root.left = createTree(str);//递归创建左树
root.right = createTree(str);//递归创建右树
}else {//当字符是 # 时，该在if else循环外已经被置为null了，直接++遍历下一个字符
i++;
}
//3. 返回根节点
return root;
}
public static void inorder(TreeNode root){//进行中序遍历
if (root == null){
return;
}
inorder(root.left);//递归遍历树的左子树
System.out.print(root.val + " ");//打印根节点
inorder(root.right);//左子树遍历完了，遍历右子树
}
}
7. 二叉树的分层遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
难点：如何确定每一层的节点个数
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
思路：
创建一个队列，用于储存每一层二叉树的结点，每一次当将头元素进行出队后，又会将下一层的结点进行入队，然后依次进行遍历，直到队列为null则结束循环
先将根节点root进入到该队列，创建一个list顺序表里面的元素也为顺序表，每一个元素用于储存每一层的结点。
此后会在一个while循环里对该二叉树进行遍历，结束循环的条件为队列为空，
做法为：
- 每一次循环都会求一次队列的长度
- 创建一个顺序表tmp进行储存该层结点
- 在循环里再来一个循环，目的是，把当前队列里存储的结点出队到tmp里面进行存储
- 把下一层二叉树的结点进行入队
- 该内while循环结束后tmp里面储存的就是该层的二叉树的所有元素
- 此时再将tmp添加到list顺序表里即可
- 此时第一层二叉树遍历完毕，队列不为空
- 继续执行外层循环
- 直到队列为空，内层循环结束，将这一层树的值存到ret顺序表里
- 外层循环也结束，返回ret
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<>();//创建一个list顺序表里面的元素也为顺序表，每一个元素用于储存每一层的结点的val值
if(root == null) {//当树为空
return ret;
}
Queue<TreeNode> queue = new LinkedList<>();//创建一个队列
queue.offer(root);//将树放进队列
while (!queue.isEmpty()){//当队列不为空的时候，对二叉树进行遍历
int size = queue.size();//用来统计队列的大小
List<Integer> tmp = new ArrayList<>();//创建一个顺序表tmp进行储存该层结点的val
while (size != 0){//当每层对应的队列不为空时
TreeNode cur = queue.poll();//出队列，用cur来接收
tmp.add(cur.val);//储存该层结点的val到该层的tmp中
size--;
if (cur.left != null){//当树的左子树不为空时，把它放进队列
queue.offer(cur.left);
}
if (cur.right != null){//当树的右子树不为空时，把它放进队列
queue.offer(cur.right);
}
}
ret.add(tmp);//一层遍历完了将该层遍历的结果存进ret中
}
return ret;
}
}
8. 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1
思路一：
root遍历这颗树，遇到 p 或者 q 就返回：
- 如果root节点是 p 或者q当中的一个，那么root就是最近公共祖先
-
如果 p 和 q 分布在root的左右两侧，那么root就是最近公共祖先
-
当 p 和·q在root的同一侧时，第一个（p / q）的节点就是最近公共祖先。
-
两边返回都不为空时，root就是最近公共祖先。
- 如果该树是一个空树，则没有最近公共祖先，直接返回null
- 如果root节点是 p 或者q当中的一个，那么root就是最近公共祖先，返回root
- 递归在root的左右树中查找p ，q,并用leftTree和rightTree来接收返回的root
- 如果 p 和 q 分布在root的左右两侧，那么root就是最近公共祖先，直接返回root
- 当左边不为空时，该节点就是最近公共祖先，返回root
- 当右边不为空时，该节点就是最近公共祖先，返回root
代码实现
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null){//空树没有最近公共祖先
return null;
}
if (root == p || root == q){//如果root节点是 p 或者q当中的一个，那么root就是最近公共祖先
return root;
}
TreeNode leftTree = lowestCommonAncestor(root.left,p,q);//在root的左树中查找p ，q,并用leftTree来接收返回的root
TreeNode rightTree = lowestCommonAncestor(root.right,p,q);//在root的右树中查找p ，q,并用rightTree来接收返回的root
if (leftTree != null && rightTree != null){//如果 p 和 q 分布在root的左右两侧，那么root就是最近公共祖先
return root;
}else if (leftTree != null){//左边不为空时，该节点就是最近公共祖先
return leftTree;
}else {//右边不为空时，该节点就是最近公共祖先
return rightTree;
}
}
}
思路二：
相当于链表的交点（二叉树里没有prve指针，所以用两个栈来实现）
栈1用于存储找到p结点的路径
栈2用于存储找到q结点的路径
然后对两个栈求长度，把栈长度比较长的栈进行出栈，直到两个栈长度相等
然后同时出栈进行一一比对，相同则为p、q的最近公共祖先
这种思路的解题难点在于如何找到p、q的路径并放入栈中：
首先需要对当前根节点进行判断，若不为空，且不是我们要找的p或q就入栈
然后再对该节点的左子树和右子树进行相同的操作，但当当前根节点的左右子树都为空时把这个节点出栈
- 写一个getPath方法来找到p、q的路径并放入栈中
- 当该节点为空或者要找节点返回false
- 如果不满足条件则将该节点进行入栈操作
- 如果在根节点的左边找到了，则返回true
- 如果在根节点的右边找到了，则返回true
- 在该root节点的左边和右边都没有找到node节点，将该root节点进行入栈操作
- 分别创建栈P和Q用于存储找到p、q结点的路径
- 调用getPath方法来找到p、q结点的路径
- 计算P栈、Q栈的长度
- 如果sizeP > sizeQ，sizeP中出差值个元素
- 如果sizeQ > sizeP，sizeQ中出差值个元素
- 当stackP和stackQ都不为空时，如果栈的元素一样，返回这个元素
- 否则stackP和stackQ都出一个元素
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null){//空树没有最近公共祖先
return null;
}
Stack<TreeNode> stackP = new Stack<>();//创建栈P用于存储找到p结点的路径
Stack<TreeNode> stackQ = new Stack<>();//创建栈Q用于存储找到q结点的路径
getPath(root,p,stackP);//找到p结点的路径
getPath(root,q,stackQ);//找到Q结点的路径
int sizeP = stackP.size();//计算P栈的长度
int sizeQ = stackQ.size();//计算Q栈的长度
if (sizeP > sizeQ){// 如果sizeP > sizeQ，sizeP中出差值个元素
int size = sizeP -sizeQ;
while (size != 0){
stackP.pop();
size--;
}
}
else {//如果sizeQ > sizeP，sizeQ中出差值个元素
int size = sizeQ -sizeP;
while (size != 0){
stackQ.pop();
size--;
}
}
//两个栈的元素一样多时
while (!stackP.isEmpty() && !stackQ.isEmpty()){
if (stackP.peek() == stackQ.peek()){//栈的元素一样，返回这个元素
return stackP.peek();
}else {//否则stackP和stackQ都出一个元素
stackP.pop();
stackQ.pop();
}
}
return null;//没有最近公共祖先（题目中不可能出现）
}
private boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode> stack){
if (root == null || node == null){//当该节点为空或者要找节点返回false
return false;
}
stack.push(root);// 如果不满足if条件则将该节点进行入栈操作
if (root == node){//如果root节点是要找的节点，返回true
return true;
}
boolean flg1 = getPath(root.left,node,stack);//到该root节点的左边找node节点，并将返回值放到flg1中
if (flg1){//如果在根节点的左边找到了，则返回true
return true;
}
boolean flg2 = getPath(root.right,node,stack);//到该root节点的右边找node节点，并将返回值放到flg2中
if (flg2){//如果在根节点的右边找到了，则返回true
return true;
}
stack.pop();//在该root节点的左边和右边都没有找到node节点，将该root节点进行出栈操作
return false;
}
}
9. 根据一棵树的前序遍历与中序遍历构造二叉树（ * * * ）
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]
思路：
知道前序遍历里面第一个存储的是我们的根节点
那就可以在我们中序遍历中找到该结点并命名为ri，则该结点两边就为该根节点的左右子树
设中序遍历开头的节点为ib，结尾的节点为ie，并且可得该节点左右子树的范围分别为 ib – ri - 1 和 ri + 1 --ie
i 后移一位后 的 F为下一个节点然后递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置
代码实现：
class Solution {
public int preIndex;//定义为成员变量才能让preIndex正常移动
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTreeChiLde(preorder,inorder,0,inorder.length - 1);
}
private TreeNode buildTreeChiLde(int[] preorder,int[] inorder,int inBegin,int inEnd){
if (inBegin > inEnd){//当inBegin > inEnd时没有左树或者没有右树
return null;
}
TreeNode root = new TreeNode(preorder[preIndex]);//前序遍历里面第一个存储的是我们的根节点
int rootIndex = findIndexRoot(inorder,inBegin,inEnd,preorder[preIndex]);//在中序遍历中inBegin到inEnd的范围里找到该根结点preorder[preIndex]
if (rootIndex == -1){//没有找到要找的节点
return null;
}
preIndex++;//前序遍历向后移动一位
//递归地对构造出左子树和右子树
root.left = buildTreeChiLde(preorder,inorder,inBegin,rootIndex - 1);// 左子树的范围为 ib -- ri - 1
root.right = buildTreeChiLde(preorder,inorder,rootIndex + 1,inEnd);// 左子树的范围为 ri + 1 --ie
return root;
}
public int findIndexRoot(int[] inorder,int inBegin,int inEnd,int key){
for (int i = inBegin; i <= inEnd; i++) {
if (inorder[i] == key){
return i;
}
}
return -1;//没有找到，返回-1
}
}
10. 根据一棵树的中序遍历后序遍历构造二叉树
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
示例 1:
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]
示例 2:
输入：inorder = [-1], postorder = [-1]
输出：[-1]
思路：
与从前序与中序遍历序列构造二叉树实现类似，只是在创建根节点左右树的时候先创建右树
class Solution {
public int postIndex;//定义为成员变量才能让postIndex正常移动
public TreeNode buildTree(int[] inorder, int[] postorder) {
postIndex =postorder.length - 1;
return buildTreeChiLde(postorder,inorder,0,inorder.length - 1);
}
private TreeNode buildTreeChiLde(int[] postorder ,int[] inorder,int inBegin,int inEnd){
if (inBegin > inEnd){//当inBegin > inEnd时没有左树或者没有右树
return null;
}
TreeNode root = new TreeNode(postorder[postIndex]);//后序遍历里面倒数第一个存储的是我们的根节点
int rootIndex = findIndexRoot(inorder,inBegin,inEnd,postorder[postIndex]);//在中序遍历中inBegin到inEnd的范围里找到该根结点preorder[preIndex]
if (rootIndex == -1){//没有找到要找的节点
return null;
}
postIndex--;//后序遍历向前移动一位
//递归地对构造出右子树和左子树
root.right = buildTreeChiLde(postorder,inorder,rootIndex + 1,inEnd);// 右子树的范围为 ri + 1 --ie
root.left = buildTreeChiLde(postorder,inorder,inBegin,rootIndex - 1);// 左子树的范围为 ib -- ri - 1
return root;
}
public int findIndexRoot(int[] inorder,int inBegin,int inEnd,int key){
for (int i = inBegin; i <= inEnd; i++) {
if (inorder[i] == key){
return i;
}
}
return -1;//没有找到，返回-1
}
}
11. 二叉树创建字符串
给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
空节点使用一对空括号对 “()” 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
示例 1：
输入：root = [1,2,3,4]
输出：“1(2(4))(3)”
解释：初步转化后得到 “1(2(4)())(3()())” ，但省略所有不必要的空括号对后，字符串应该是"1(2(4))(3)" 。
示例 2：
输入：root = [1,2,3,null,4]
输出：“1(2()(4))(3)”
解释：和第一个示例类似，但是无法省略第一个空括号对，否则会破坏输入与输出一一映射的关系。
思路：
递归的方法得到二叉树的前序遍历，并在递归时加上额外的括号
根节点直接拼接，根据前序遍历的结果，遇到节点拼接左括号（ 和该节点。
- 如果当前节点有两个子树，那我们在递归时，需要在两个孩子的结果外都加上一层括号； 如果当前节点没有子树，那我们不需要在节点后面加上任何括号
- 如果当前节点只有左子树，那我们在递归时，只需要在左子树的结果外加上一层括号，而不需要给右子树加上任何括号；
- 如果当前节点只有右子树，那我们在递归时，需要先加上一层空的括号 表示左子树为空，再对右子树进行递归，并在结果外加上一层括号。
- 创建一个StringBuilder 类型的变量用来拼接字符串
- 调用tree2strChild来进行根据二叉树创建字符串
- 为空树时，不进行字符串的创建
- 如果根节点的左子树不为空，拼接一个左括号
- 遍历当前根节点的左子树
- 最后在加一个右括号表示左子树遍历结束
- 如果根节点的左子树为空，并且根节点的右子树也为空，直接返回表示左边走完了
- 如果右子树不为空，直接加一对括号
- 创建右子树与左子树类似，只是在根节点的右子树为空时直接返回
- 把StringBuilder 类型的变量转化为String类
class Solution {
public String tree2str(TreeNode root) {
StringBuilder stringBuilder = new StringBuilder();//创建一个StringBuilder 类型的变量用来拼接字符串
tree2strChild(root,stringBuilder);//调用tree2strChild来进行根据二叉树创建字符串
return stringBuilder.toString();//把StringBuilder 类型的变量转化为String类
}
private void tree2strChild(TreeNode treeNode,StringBuilder stringBuilder){
if(treeNode == null){//为空树时，不进行字符串的创建
return;
}
stringBuilder.append(treeNode.val);//根节点直接拼接
if (treeNode.left != null){//如果根节点的左子树不为空
stringBuilder.append("(");//拼接一个左括号
tree2strChild(treeNode.left,stringBuilder);//遍历当前根节点的左子树
stringBuilder.append(")");//最后在加一个右括号表示左子树遍历结束
}else {//如果根节点的左子树为空
if (treeNode.right == null){///如果根节点的右子树也为空，直接返回表示左边走完了
return;
}else {//如果右子树不为空
stringBuilder.append("()");//直接加一对括号
}
}
//判断右树
if (treeNode.right != null){//如果根节点的右子树不为空
stringBuilder.append("(");//拼接一个右括号
tree2strChild(treeNode.right,stringBuilder);//遍历当前根节点的右子树
stringBuilder.append(")");//最后在加一个右括号表示右子树遍历结束
}else {//如果根节点的左子树为空
return;
}
}
}
12. 二叉树前序递归遍历实现
方法一：遍历到是就存
class Solution {
List<Integer> ret = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {//把前序遍历的结果存储到list当中。
//后序遍历(Postorder Traversal): 根的左子树--->根的右子树--->根节点
if(root == null) {//当树为空
return ret;
}
ret.add(root.val);//存根
preorderTraversal(root.left);//递归遍历树的左子树
preorderTraversal(root.right);//左子树遍历完了，遍历右子树
return ret;
}
}
方法二（利用返回值）
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {//把前序遍历的结果存储到list当中。
//后序遍历(Postorder Traversal): 根的左子树--->根的右子树--->根节点
List<Integer> list = new ArrayList<>();
if(root == null) {//当树为空
return list;
}
list.add(root.val);//存根
List<Integer> leftTree = preorderTraversal(root.left);//递归遍历树的左子树
list.addAll(leftTree);
List<Integer> rightTree = preorderTraversal(root.right);//左子树遍历完了，遍历右子树
list.addAll(rightTree);
return list;
}
}
13. 二叉树前非递归遍历实现
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[1,2]
示例 5：
输入：root = [1,null,2]
输出：[1,2]
思路：
用一个栈来存放二叉树遍历的结果，前序遍历遇到一个节点不为空就将它存到栈中并打印
当遍历到的节点为空时，从栈中弹出一个元素，判断其右子树是否为空，如果不为空就执行上面的操作，如果为空则弹出这个节点并对该节点的右子树进行相同的操作。
- 当树为空，不能创建，直接返回
- 创建一个栈用来进行树的非递归前序遍历
- 前序遍历（双层循环）这颗树当当前节点不为空，将它存进栈中,并进行打印
- 判断当前节点的左子树是否满足条件
- 内循环结束，说明当前节点的左子树遍历完了，它的右边
void preOrderNor(TreeNode root){//非递归前序遍历
// 前序遍历 根 -》 左子树 -> 右子树 (递归)
if(root == null) {//当树为空
return;
}
Stack<TreeNode> stack = new Stack<>();//创建一个栈用来进行树的非递归前序遍历
TreeNode cur = root;
while (cur != null || !stack.isEmpty()){//当当前节点不为空,或者栈不为空
while (cur != null){//当当前节点不为空，将它存进栈中,并进行打印
stack.push(cur);
System.out.print(cur.val + " ");
cur = cur.left;//判断当前节点的左子树是否满足条件
}
//判断左子树遍历完的节点的右边
TreeNode top = stack.pop();
cur = top.right;///判断左子树遍历完的节点的右边
}
}
14. 二叉树中序非递归遍历实现
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
思路：
与二叉树前非递归遍历实现相似，只是打印的时间不一样，只有左边遍历结束才开始打印
void inOrderNor(TreeNode root){//非递归中序遍历
//中序遍历:根的左子树--->根节点--->根的右子树
if(root == null) {//当树为空
return;
}
Stack<TreeNode> stack = new Stack<>();//创建一个栈用来进行树的非递归中序遍历
TreeNode cur = root;
while (cur != null || !stack.isEmpty()){//当当前节点不为空,或者栈不为空
while (cur != null){//当当前节点不为空，将它存进栈中,并进行打印
stack.push(cur);
cur = cur.left;//判断当前节点的左子树是否满足条件
}
//左子树遍历结束，弹出栈顶元素并打印，判断左子树遍历完的节点的右边
TreeNode top = stack.pop();
System.out.print(top.val + " ");
cur = top.right;///判断左子树遍历完的节点的右边
}
}
15. 二叉树后序非递归遍历实现
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[3,2,1]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
思路：
入栈思路与前序遍历和中序遍历思路相同，只是出栈和打印的时间不同
首先需要得到栈顶元素，但不出栈，依旧用top表示
如果top右节点为null，则说明top为叶子结点，top可以出栈并打印
如果不为null，则遍历top的右节点
void postOrderNor(TreeNode root){//非递归后序遍历
//后序遍历(Postorder Traversal): 根的左子树--->根的右子树--->根节点
if(root == null) {//当树为空
return;
}
TreeNode prev = null;//用来记录最新打印了的节点(要放在循环外)
Stack<TreeNode> stack = new Stack<>();//创建一个栈用来进行树的非递归后序遍历
TreeNode cur = root;
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){//它的右边为空时,打印栈顶元素并弹出
System.out.print(top.val + " ");
stack.pop();
prev = top;//记录最新打印了的节点
}else{//不为null，则遍历top的右节点
cur = top.right;//遍历top的右节点
}
}
}
16. 二叉树的最大深度
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：3
示例 2：
输入：root = [1,null,2]
class Solution {
public int maxDepth(TreeNode root) {
if (root == null){//树没有节点返回0
return 0;
}
int leftHeight = maxDepth(root.left);//递归遍历树的左子树并统计左子树的高度
int rightHeight = maxDepth(root.right);//左子树遍历完了，递归遍历树的右子树并统计统计右子树的高度
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;//返回左子树与右子树高度的最大值 + 1（二叉树的高度）
}
}