递归算法
**思路:**递归方法很容易理解,按照后序遍历的顺序
- 先判断是否有左子树,有的话遍历
- 判断是否有右子树,有的话遍历
- 添加根节点值到列表
import java.util.*;
public class Solution {
public int[] postorderTraversal (TreeNode root) {
// write code here
if(root==null)return new int[0];
List<Integer> list = new ArrayList<>();
postOr(list,root);
int[] res=new int[list.size()];
for(int i=0;i<res.length;i++){
res[i]=list.get(i);
}
return res;
}
//递归方法
public void postOr(List<Integer> list,TreeNode t){
if(t.left!=null) postOr(list,t.left);
if(t.right!=null) postOr(list,t.right);
list.add(t.val);
}
}
非递归算法--两个栈
思路: 这是一个非常巧妙的算法,后序遍历的顺序为左、右、根,反过来就是根、右、左,类似先序遍历的根、左、右, 先序遍历的非递归很简单:根节点入栈,出栈并依次判断右、左子树,有右入右,有左入左,然后循环出栈判断,后续遍历的反向遍历就是在 出栈判断时,先入左,后入右
import java.util.*;
public class Solution {
public int[] postorderTraversal (TreeNode root) {
// write code here
if(root==null)return new int[0];
Stack<TreeNode> s1=new Stack<>();
Stack<TreeNode> s2=new Stack<>();
TreeNode p=root;
s1.push(p);
while(!s1.empty()){
p=s1.pop();
s2.push(p);
if(p.left!=null)s1.push(p.left);
if(p.right!=null)s1.push(p.right);
}
int[] res=new int[s2.size()];
for(int i=0;i<res.length;i++){
res[i]=s2.pop().val;
}
return res;
}
}
非递归算法-一个栈
思路: 一个栈的算法就是按照后序遍历的左、右、根,老老实实的遍历,分三步走。细节是设定一个指针,始终跟随上一个输出的元素,然后与下一个弹出节点的左右子树进行比较,来判断该弹出节点的左右子树是否已经遍历过了。
- 判断左子树是否为空,以及上一个弹出节点是否为左子树,以及是否为右子树。
- 进入2,说明左子树为空,或遍历过了,判断右子树是否为空,以及上一个弹出节点是否为右子树
- 进入3,说明左右子树都遍历过或者为空,那么就弹出该节点,然后指针指向该弹出节点
import java.util.*;
public class Solution {
public int[] postorderTraversal (TreeNode root) {
// write code here
if(root==null)return new int[0];
Stack<TreeNode> s=new Stack<>();
List<Integer> list=new ArrayList<>();
//定义两个指针,t指向栈顶,c指向刚出栈的节点,初始都指向root
TreeNode t=root;
TreeNode c=root;
s.push(t);
//进入循环,判断条件栈不为空
while(!s.empty()){
//t赋值为栈顶元素
t=s.peek();
//判断左子树是否为空,以及上一个弹出节点是否为左子树,以及是否为右子树
if(t.left!=null&&c!=t.left&&c!=t.right){
s.push(t.left);
//判断右子树是否为空,以及上一个弹出节点是否为右子树
}else if(t.right!=null&&c!=t.right){
s.push(t.right);
//弹出该节点,然后指针指向该弹出节点
}else{
list.add(t.val);
s.pop();
c=t;
}
}
int[] res=new int[list.size()];
for(int i=0;i<res.length;i++){
res[i]=list.get(i);
}
return res;
}
}