NC192 二叉树的后序遍历

NC192 二叉树的后序遍历

二叉树的后序遍历_牛客题霸_牛客网 (nowcoder.com)

145. 二叉树的后序遍历

145. 二叉树的后序遍历 - 力扣（LeetCode）

// //递归
// import java.util.*;
// public class Solution {
//     public void postorder(TreeNode root,List<Integer> list){
//         if(root==null){
//             return;
//         }
//         postorder(root.left,list);
//         postorder(root.right,list);
//         list.add(root.val);
//     }
//     public int[] postorderTraversal (TreeNode root) {
//         List<Integer> list=new ArrayList<>();
//         postorder(root,list);
//         //
//         int[] ret=new int[list.size()];
//         for(int i=0;i<list.size();i++){
//             ret[i]=list.get(i);
//         }
//         return ret;
//     }
// }


//后序遍历-左右根
//迭代
import java.util.*;
public class Solution {
    public int[] postorderTraversal (TreeNode root) {
        List<Integer> list=new ArrayList<>();
        Stack<TreeNode> st=new Stack<TreeNode>();
        TreeNode prev=null;
        while(root!=null||st.isEmpty()==false){
            while(root!=null){
                st.push(root);
                root=root.left;
            }
            TreeNode cur=st.pop();
            if(cur.right==null||cur.right==prev){
                list.add(cur.val);
                prev=cur;
            }else{
                st.push(cur);
                root=cur.right;
            }
        }
        //
        int[] ret=new int[list.size()];
        for(int i=0;i<list.size();i++){
            ret[i]=list.get(i);
        }
        return ret;
    }
}