4.1 100. 相同的树 - 力扣（LeetCode）
分析：本题是要判断一颗树是否相同，这里的相同指的是树的数值和结构都是相同的。
如图：结构和数值均相同才是两颗相同的树。
不相同的情况：
1、一棵树的结点为空，另一棵树的结点不为空。
2、两棵树的结点均不为空，但是值不相同。
解题思路：先判断结点是否为空（防止空指针异常）：若一个结点为空，另一个结点不为空，说明不是同一棵树，返回false；若两个结点均为空，则说明是同一棵树，返回true。然后判断值是否相同，最后采用前序遍历，遍历两棵树的左子树和右子树。
//判断两棵树是否为相同树
//时间复杂度：设p有M个元素，q有N个元素，时间复杂度为min（m，n）;
public boolean isSameTree(BinaryTree.TreeNode p, BinaryTree.TreeNode q) {
//1、一颗树为空一棵树不为空
//2、虽然两棵树都不为空但是值不相同
//建议采用前序遍历：根左右
if(p == null && q != null || q == null && p != null){
return false;
}
//两个都为空认为是两棵相同的树
if(p == null && q== null){
return true;
}
//两个都不为空
if(p.val != q.val) return false;
//左树和右树均为true则是两颗相同的树
return isSameTree(p.left,q.left)
&& isSameTree(p.right,q.right);
}这里还需要补充一句：若树p中有m个结点，q中有n个结点，时间复杂度为min（m,n）。
4.2 572. 另一棵树的子树 - 力扣（LeetCode）
分析：本题是要求一棵树中是否包含给定子树，即判断root中是否存在subRoot（值和结构都要相同）。
如下图：root中存在subRoot
如下图：root中不包含subRoot（2多了个左孩子0）
还有一种情况：就是root和subRoot相同，这样也算subRoot是root的子树
这最后的一种情况也为我们解题提供了一种思路：我们可以使用第一题的判断两棵树的是否相同的函数，如果一开始的root与Subroot不相同，那么就遍历root的左子树和右子树，看root的左子树和右子树是否与subRoot相同。
public boolean isSameTree(TreeNode p, TreeNode q) {
//1、一颗树为空一棵树不为空
//2、虽然两棵树都不为空但是值不相同
//建议采用前序遍历：根左右
//时间复杂度：设p有M个元素，q有N个元素，时间复杂度为min（m，n）;
if(p == null && q !=null ||q == null && p != null){
return false;
}
//两个都为空认为是两棵相同的树
if(p == null && q == null){
return true;
}
//两个都不为空
if(p.val != q.val){
return false;
}
//左树和右树均为true则是两颗相同的树
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
//1、根节点和子树相不相同
//2、subRoot是不是root.left的子树
//3、subRoot是不是 root.right的子树
//root:s subRoot:r 时间复杂度：r*s（每个节点都需要判断是否与subRoot相同）
//判断root是否为空，防止空指针异常
if(root == 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;
}4.3 226. 翻转二叉树 - 力扣（LeetCode）
分析：如图，本题需要将左右子树的所有节点进行交换，注意这里需要交换的是节点，不是节点的值。
解题思路：定义一个节点tmp，对root的左右节点进行交换，再遍历左、右子树，对左、右子树的每一个节点分别进行交换。
public TreeNode invertTree(TreeNode root) {
//交换的是地址
//每一颗子树都去交换左右孩子的指向 遍历二叉树的所有结点
if(root == null) return null;
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}4.4 110. 平衡二叉树 - 力扣（LeetCode）
分析：首先，什么是平衡二叉树？平衡二叉树是指每个节点的左子树和右子树高度差的绝对值不超过1，且左、右子树也都是平衡二叉树。
如下图：3的左子树高度为1，右子树高度为2，高度差的绝对值为1，20的左子树高度为1，右子树高度为1，高度差为0，所以这是一颗平衡二叉树。
下面来看一组不是平衡二叉树的例子，如下图：虽然3的左子树和右子树高度差为1，但是9的左右子树高度差为2，所以这棵树不是平衡二叉树。
解题思路：先遍历求每棵二叉树的高度的高度（求二叉树的高度在上一篇文章中已经讲过：CSDN，这里就不做过多赘述），然后再遍历一次二叉树看每棵二叉树的高度差的绝对值是否小于等于1。
//求二叉树的高度
public int getHeight(TreeNode root){
if(root == null) return 0;
int leftTree = getHeight(root.left);
int rightTree = getHeight(root.right);
//左子树和右子树高度的最大值+1就是二叉树的高度
return leftTree > rightTree? leftTree+1 : rightTree+1;
}
//判断是否是平衡二叉树
public boolean isBalanced(TreeNode root) {
if(root == null)return true;
int leftTree = getHeight(root.left);
int rightTree = getHeight(root.right);
//当前根高度差是否小于1，遍历每棵子树进行判断
return Math.abs(leftTree-rightTree) <= 1
&& isBalanced(root.left)
&& isBalanced(root.right);
}通过上述代码，我们需要遍历两次二叉树，那么有没有只遍历一次二叉树就可以求出它是不是平衡二叉树的方法呢？我们能不能在求高度的同时就判断它子树的高度差的绝对值是否小于等于1呢？当然是可以的，我们只需要把求二叉树高度的代码改为是平衡二叉树返回正常高度，不是平衡二叉树返回-1，最后在判断平衡二叉树的代码中判断高度是否大于等于0就ok了。
public int getHeight(TreeNode root){
if(root == null) return 0;
//左子树的高度
int leftHeight = getHeight(root.left);
//右子树的高度
int rightHeight = getHeight(root.right);
//在判断子树的同时就可以得出是不是平衡二叉树
//所以如果左子树/右子树返回值<0就说明不是平衡二叉树，无需在进行判断
//高度差绝对值大于1，不是平衡二叉树
if(leftHeight >= 0 && rightHeight >= 0 && Math.abs(leftHeight - rightHeight)<=1){
return Math.max(leftHeight,rightHeight)+1;
}else{
return -1;
}
}
public boolean isBalanced(TreeNode root) {
//结论：只有每一棵子树都是高度平衡的才能说这棵树是高度平衡的
//判断：高度差小于1 && 左树是平衡的（递归继续求高度）&& 右树也是平衡的（递归继续求高度）
//最大问题：重复计算（效率低）->在判断父亲的同时判断子树平不平衡
//能否在求高度的时候就知道这棵树是否平衡
//我拿着 你求得高度的值 去判断 当前高度<=1吗
if(root == null) return true;
return getHeight(root) > 04.5 101. 对称二叉树 - 力扣（LeetCode）
分析：本体需要判断一棵二叉树是否对称，那么什么情况是不对称的呢？
1、一边有节点，一边没节点。
2、节点的值不同。
解题思路：由于同时遍历左树和右树进行判断，因此一个节点肯定不够，所以我们需要两个节点进行判断，所以我们需要重新写一个参数为两个节点的函数进行判断，判断的代码与4.1一摸一样。
需要注意的是：这里判断对称二叉树的时候是要左根的右子树和右根的左子树以及右根的左子树和左根的右子树进行判断。
//需要左右两个节点进行判断
//因此需要再写一个方法
public boolean isSymmetric(TreeNode root) {
if(root == null) return true;
return isSymmetricChild(root.left,root.right);
}
public boolean isSymmetricChild(TreeNode p,TreeNode q){
//一边为空一边不为空
if(p == null && q != null || q == null && p != null ){
return false;
}
if(p == null && q ==null){
return true;
}
if(p.val != q.val){
return false;
}
return isSymmetricChild(p.left,q.right)&&isSymmetricChild(p.right,q.left);
}4.6 二叉树遍历_牛客题霸_牛客网 (nowcoder.com)
分析：本题需要先序遍历创建一颗二叉树（节点的值由用户输入），然后使用中序遍历将其输出 。
解题思路：首先，因为本题使用的是牛客的ACM模式，所以我们需要创建节点类（依据题意可知节点的值为字符型）。
class TreeNode{
char val;
TreeNode left;
TreeNode right;
TreeNode(char val){
this.val = val;
}
}由刚才的分析我们可以知道在main函数中我们需要先创建一个二叉树，所以要先写一个creatTree（）方法，再把它的返回值给到inOrder()方法进行遍历。
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextLine()) { // 注意 while 处理多个 case
String s = in.nextLine();
TreeNode ret = creatTree(s);
inOrder(ret);
}
}先写中序遍历的方法，因为在之前的文章已经讲解过这里就不做过多赘述。
//中序遍历
public static void inOrder(TreeNode root){
if(root == null) return;
inOrder(root.left);
System.out.print(root.val+" ");
inOrder(root.right);
}接下来也是最重要的一步：先序遍历创建二叉树。首先，定义一个成员变量i遍历字符串，遍历到非‘#’则创建一个新节点，把i的值存储进去，然后先创建左子树，再创建右子树，如果遍历到‘#’，则让i++即可。
//先序遍历 创建二叉树
public static TreeNode creatTree(String s){
TreeNode root = null;
if(s.charAt(i) != '#'){
root = new TreeNode(s.charAt(i));
i++;
//递归创建左子树
root.left = creatTree(s);
//递归创建右子树
root.right = creatTree(s);
//注意，向后递的过程是一直创建结点的过程，往回归的时候才是结点直接进行连接的过程
}else{//说明遇到空了直接让i往后走
i++;
}
return root;
}这道题还有两点注意：1、我们并不是使用字符串的遍历来遍历这个字符串而是使用前序遍历来遍历这个字符串，因此并不需要担心越界。2、并不是在递推的过程中就把树串起来的，递推只是创建节点的过程，回归时才把节点串起来。
完整代码：
import java.util.Scanner;
class TreeNode{
char val;
TreeNode left;
TreeNode right;
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 s = in.nextLine();
TreeNode ret = creatTree(s);
inOrder(ret);
}
}
private static int i;
//先序遍历 创建二叉树
public static TreeNode creatTree(String s){
TreeNode root = null;
if(s.charAt(i) != '#'){
root = new TreeNode(s.charAt(i));
i++;
//递归创建左子树
root.left = creatTree(s);
//递归创建右子树
root.right = creatTree(s);
//注意，向后递的过程是一直创建结点的过程，往回归的时候才是结点直接进行连接的过程
}else{//说明遇到空了直接让i往后走
i++;
}
return root;
}
//中序遍历
public static void inOrder(TreeNode root){
if(root == null) return;
inOrder(root.left);
System.out.print(root.val+" ");
inOrder(root.right);
}
}4.7 102. 二叉树的层序遍历 - 力扣（LeetCode）
在上一篇博客中：CSDN，我们已经知道二叉树的层序遍历需要依靠队列实现，但这道题的不同之处在于，他要将层序遍历的结果存储在二维数组中， 所以我们需要求当前队列中的元素个数，这样做才能把同一层的节点输出。同一层的节点放到同一行后，再把它放入二维数组中即可。
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()) {
//ret会随着出栈元素的变化而变化
//求一下当前队列的大小
int size = queue.size();
List<Integer> row = new ArrayList<>();
//只有将当前行入链表完才会执行外部循环
while (size != 0) {
//也就是出队列4次 相当于把这层节点都出队了
TreeNode cur = queue.poll();
row.add(cur.val);
size--;
if(cur.left != null){
queue.offer(cur.left);
}
if (cur.right != null){
queue.offer(cur.right);
}
}
ret.add(row);
}
return ret;
}4.8 236. 二叉树的最近公共祖先 - 力扣（LeetCode）
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。
如下图所示：若输入5和1，输出最近公共祖先为3。
若输入5和4，输出公共祖先为5，根据定义：一个节点也可以是自己的祖先。
为了能够更好地理解此题，这里需要引入二叉搜索树地概念：根的左边比根小，根的右边比根大，这就是二叉搜索树。 如下图，为一棵二叉搜索树：
有以下三种情况：
1、p == root || q == root,则公共祖先为root。
2、p.val < root.val && q.val > root.val 此时p在root的左边，q在root的右边 则公共祖先是root。
3、 p.val < root.val && q.val < root.val 此时p和q在root的同一侧。这种情况，就需要递归到root中（先找左树再找右树）当中去查找 。
下面是递推的过程：
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) return null;
if(p == root || q == root){
return root;
}
//看左子树有没有找到节点
TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
//看右子树有没有找到节点
TreeNode rightTree = lowestCommonAncestor(root.right,p,q);
if(leftTree != null && rightTree != null){
//第二种情况：在根的两侧返回根
return root;
}else if(leftTree != null){
//说明都在root的左子树中
return leftTree;
}else{
return rightTree;
}
}解这道题还有第二种解法：
如果二叉树保留了父亲节点的地址，那么这个题可转变为求链表的相交节点，详见CSDN
现在问题的难点在于：如何找到根节点到指定节点路径上的所有节点？
这时我们会想到栈这种先进后出的数据结构：可以使用栈存储，先出差值个，然后同时出，相同的那个就是最近祖先。
public TreeNode lowestCommonAncestor(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();
//让长度长的栈先出差值个yuansu
if(sizeP > sizeQ){
int size = sizeP - sizeQ;
while(size != 0){
stackP.pop();
size--;
}
}else{
int size = sizeQ - sizeP;
while(size != 0){
stackQ.pop();
size--;
}
}
//两个栈元素是相同的
while(!stackP.isEmpty() && !stackQ.isEmpty()){
//找到相交的节点返回就是最近的祖先
//注意栈里存放的是对象的引用
if(stackP.peek().equals(stackQ.peek())){
return stackP.peek();
}
stackP.pop();
stackQ.pop();
}
return null;
}
//找到root到node路径上的所有节点存储到stack中
private boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode> stack){
if(root == null || node == null){
return false;
}
//先将遍历到的节点入栈，再进行判断
stack.push(root);
if(root == node){//说明root已经找到当前的节点了
return true;
}
boolean flg = getPath(root.left,node,stack);
if(flg){
return true;
}
boolean flg2 = getPath(root.right,node,stack);
if(flg2){
return true;
}
//如果左右都没找到说明一定不是你路径上的节点
//那么就出栈并且返回flase
stack.pop();
return false;
}4.9 105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）
分析：这道题是我们之前的选择题，需要我们写一个代码来实现构造二叉树的功能，在当时我们讲过：要通过前序遍历确定节点出现的顺序，通过中序遍历确定它的左右节点。
由此我们可以知道：我们在前序遍历需要一个下标（pi）来确定出现的顺序，在中序遍历种需要三个下标（ib、ri、ie）来确定左右节点和根，ri为pi所找到的当前的根节点下标。
然后递归创建左子树（ie = 之前的ri - 1）和右子树（ib = 之前的ri + 1）。
由上述分析，我们可知，完成这项功能需要下标参数，但力扣给出的原始代码并没有给出，所以我们需要自己写一个有下标参数的方法。
我们知道创建一棵二叉树一定是递归实现的,递归需要的最重要的一点就是递归出口，那么对于这道题来说，递归出口是什么呢？
当创建完F这棵树之后，在创建H这棵左子树的时候，其ie 为 ri -1，即再创建H这棵子树的时候，H的ib 和 ie 相同了，当ie == ib的时候，说明此时只有一个结点了，但这个结点也是需要创建的。
如果ri没有左子树H，那么ib == ri ，此时ie在I的位置，若此时要创建F的左子树，ie = ri-1，此时我们会发现ib>ie，不符合创建节点的条件。所以，当ib > ie时，说明没有左节点。
同理，当没有右节点时，ie == ri,此时，当要创建右节点时ib == ri+1，此时，同样会出现ib>ie的情况。综上所述，递归的出口就是：ib > ie。
接下来第二步：先序遍历数组创建根节点，代码如下图所示：第①步为递归出口，第②步为创建根节点的过程。
第三步：找到当前根节点在中序遍历中的位置，返回下标i，如果下标为-1，说明没有找到返回null。
第四步：让preIndex下标往后走。
第五步：递归创建左、右子树后，返回根节点。
但是上面的代码通过不了全部的测试用例，问题出在preIndex这里，我们原本的预期是让preIndex从0走到preorder.length-1,遍历完整个preorder数组。
但是，在buildTreeChild方法中，priIndex是作为一个局部变量参数出现的，局部变量的生命周期的随着方法结束而结束的，在递归过程中，我们的预期结果根据先序遍历，pi = 1创建F，pi = 2 创建H，然后回归到F，pi再等于 3创建I，但在H回归到F的时候，pi是局部变量，pi由H的2又变回的F的1，导致无法像预期一样到 3 ，创建I。
所以我们这里的解决办法就是将preIndex设置为全局变量，这样preIndex就不会因为递归而改变。
完整代码奉上：
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTreeChild(preorder,inorder,0,inorder.length-1);
}
private int preIndex;
public TreeNode buildTreeChild(int[] preorder,int[] inorder,int ib,int ie){
//说明没有左子树或者右子树
if(ib > ie){
return null;
}
//创建根节点
TreeNode root = new TreeNode(preorder[preIndex]);
//在中序遍历中找到前序遍历中当前的节点
int ri = findRootIndex(preorder,inorder,ib,ie);
if(ri == -1){
return null;
}
//preIndex往后走
preIndex++;
//创建左右子树
root.left = buildTreeChild(preorder,inorder,ib,ri-1);
root.right = buildTreeChild(preorder,inorder,ri+1,ie);
return root;
}
public int findRootIndex(int[] preorder,int[] inorder,int ib,int ie){
for(int i = ib;i <= ie;i++){
if(inorder[i] == preorder[preIndex]){
return i;
}
}
return -1;
}4.10106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）
这道题与上一题大同小异，只需要把遍历前序遍历的下标改为后序遍历的（即从数组的最后一个元素开始往前遍历）。
private int postIndex;
public TreeNode buildTree(int[] inorder, int[] postorder) {
postIndex = postorder.length-1;
return buildTreeChild(postorder,inorder,0,inorder.length-1);
}
private TreeNode buildTreeChild(int[] postorder,int[] inorder,int inbegin,int inend){
//1、没有左树 或者没有右树了
if(inbegin > inend){
return null;
}
//2、创建根节点
TreeNode root = new TreeNode(postorder[postIndex]);
//3、从中序遍历中找到根节点所在的下标
int rootIndex = findIndex(inorder,inbegin,inend,postorder[postIndex]);
if(rootIndex == -1){
return null;
}
postIndex--;
//root.left = ?
//root.right = ?
//创建右子树和左子树
root.right = buildTreeChild(postorder,inorder,rootIndex+1,inend);
root.left = buildTreeChild(postorder,inorder,inbegin,rootIndex-1);
return root;
}
//找到当前前序遍历的根在中序遍历中的位置，返回它的下标
private int findIndex(int[] inorder,int inbegin,int inend,int key){
//注意这里的数组长度会改变的，i不能等于0
for(int i = inbegin;i <= inend;i++){
if(inorder[i] == key){
return i;
}
}
return -1;
}4.11 606. 根据二叉树创建字符串 - 力扣（LeetCode）
这是题目的要求：
给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
示例1： 
二叉树的前序遍历为：1 2 3 4。
先在字符串中添加1。
因为2是新的一棵树，所以要添加上左括号。
同理，4也应该添加上左括号，因为4已经没有子树了，所以直接添加上右括号。
此时2也没有了右子树，表明2的子树也遍历完了，可以加右括号 。
示例2：
可以看到如果左边为空，右边不为空，需要先添加一个括号。
由以上：1、左右两边都为空，返回。
2、左边不为空 左括号+递归左边+右括号。
3、左边为空 左括号+右括号。
有代码如下：
public String tree2str(TreeNode root) {
//1、左右两边都为空 返回
//2、左边不为空
//（
//递归左边
//）
//3、左边为空但是右边不为空（）
//情况
//1、左边不为空：1、右边为空 2、右边不为空
//2、左边为空：1、右边为空 2、右边不为空
//3、右边空
//4、右边不空
StringBuilder stringBilder = new StringBuilder();
tree2strChild(root,stringBilder);
return stringBilder.toString();
}
private void tree2strChild(TreeNode t,StringBuilder stringBilder){
if(t == null){
return;
}
stringBilder.append(t.val);
//左边不为空
if(t.left != null){
stringBilder.append("(");
//递归左边
tree2strChild(t.left,stringBilder);
stringBilder.append(")");
}else{
if(t.right == null){
return;
}else{
stringBilder.append("()");
}
}
if(t.right != null){
stringBilder.append("(");
//递归右边
tree2strChild(t.right,stringBilder);
stringBilder.append(")");
}else{
return;
}
}简化代码如下：
class Solution {
public String tree2str(TreeNode root) {
if (root == null) {
return "";
}
if (root.left == null && root.right == null) {
return Integer.toString(root.val);
}
if (root.right == null) {
return new StringBuffer().append(root.val).append("(").append(tree2str(root.left)).append(")").toString();
}
return new StringBuffer().append(root.val).append("(").append(tree2str(root.left)).append(")(").append(tree2str(root.right)).append(")").toString();
}
}
4.12 144. 二叉树的前序遍历 - 力扣（LeetCode）
public List<Integer> preorderTraversal(TreeNode root) {
//1、递归
// List<Integer> ret = new ArrayList();
// if(root == null) return ret;
// ret.add(root.val);
// List<Integer> leftTree = preorderTraversal(root.left);
// ret.addAll(leftTree);
// List<Integer> rightTree = preorderTraversal(root.right);
// ret.addAll(rightTree);
// return ret;
//2、非递归
List<Integer> list = new ArrayList();
if(root == null) return list;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
TreeNode top = null;
while(cur != null || !stack.isEmpty()){
while(cur != null){
stack.push(cur);
list.add(cur.val);
cur = cur.left;
}
top = stack.pop();
cur = top.right;
}
return list;
}4.13 94. 二叉树的中序遍历 - 力扣（LeetCode）
public List<Integer> inorderTraversal(TreeNode root) {
// List<Integer> ret = new ArrayList();
// if(root == null) return ret;
// List<Integer> leftTree = inorderTraversal(root.left);
// ret.addAll(leftTree);
// ret.add(root.val);
// List<Integer> rightTree = inorderTraversal(root.right);
// ret.addAll(rightTree);
// return ret;
List<Integer> list = new ArrayList();
if(root == null) return list;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
TreeNode top = null;
while(cur != null || !stack.isEmpty()){
while(cur != null){
stack.push(cur);
cur = cur.left;
}
top = stack.pop();
list.add(top.val);
cur = top.right;
}
return list;
}4.14 145. 二叉树的后序遍历 - 力扣（LeetCode）
public List<Integer> postorderTraversal(TreeNode root) {
// //递归实现
// List<Integer> ret = new ArrayList();
// if(root == null) return ret;
// List<Integer> leftTree = postorderTraversal(root.left);
// ret.addAll(leftTree);
// List<Integer> rightTree = postorderTraversal(root.right);
// ret.addAll(rightTree);
// ret.add(root.val);
// return ret;
List<Integer> list = new ArrayList();
if(root == null) return list;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
TreeNode top = null;
TreeNode prev = null;
while(cur != null || !stack.isEmpty()){
while(cur != null){
stack.push(cur);
cur = cur.left;
}
top = stack.peek();
if(top.right == null || top.right == prev){
stack.pop();
list.add(top.val);
prev = top;
}else{
cur = top.right;
}
}
return list;
}