NC193 二叉树的前序遍历

NC193 二叉树的前序遍历

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

144. 二叉树的前序遍历

144. 二叉树的前序遍历 - 力扣（LeetCode）

// //递归
// import java.util.*;
// public class Solution {
//     public void preorder(TreeNode root,List<Integer> list){
//         if(root==null){
//             return;
//         }
//         list.add(root.val);
//         preorder(root.left,list);
//         preorder(root.right,list);
//     }
//     public int[] preorderTraversal (TreeNode root) {
//         List<Integer> list=new ArrayList<>();
//         preorder(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[] preorderTraversal (TreeNode root) {
//         if(root==null){
//             return new int[0];
//         }
//         List<Integer> list=new ArrayList<>();
//         Stack<TreeNode> st=new Stack<>();
//         st.push(root);
//         while(st.isEmpty()==false){
//             TreeNode cur=st.pop();
//             list.add(cur.val);
//             //根左右-栈-入栈先右后左
//             if(cur.right!=null){
//                 st.push(cur.right);
//             }
//             if(cur.left!=null){
//                 st.push(cur.left);
//             }
//         }
//         //
//         int[] ret=new int[list.size()];
//         for(int i=0;i<list.size();i++){
//             ret[i]=list.get(i);
//         }
//         return ret;
//     }
// }


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