递归算法


**思路:**递归方法很容易理解,按照后序遍历的顺序

  • 先判断是否有左子树,有的话遍历
  • 判断是否有右子树,有的话遍历
  • 添加根节点值到列表

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;
    }
}

非递归算法-一个栈


思路: 一个栈的算法就是按照后序遍历的左、右、根,老老实实的遍历,分三步走。细节是设定一个指针,始终跟随上一个输出的元素,然后与下一个弹出节点的左右子树进行比较,来判断该弹出节点的左右子树是否已经遍历过了。

  1. 判断左子树是否为空,以及上一个弹出节点是否为左子树,以及是否为右子树。
  2. 进入2,说明左子树为空,或遍历过了,判断右子树是否为空,以及上一个弹出节点是否为右子树
  3. 进入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;
    }
}