NC193 二叉树的前序遍历

NC193 二叉树的前序遍历

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

144. 二叉树的前序遍历

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

---

// //前序遍历-根左右
// //递归
// import java.util.*;
// public class Solution {
//     public void preorder(List<Integer> list,TreeNode root){
//         if(root==null){
//             return;
//         }
//         list.add(root.val);
//         preorder(list,root.left);
//         preorder(list,root.right);
//     }
//     public int[] preorderTraversal (TreeNode root) {
//         List<Integer> list=new ArrayList<>();
//         preorder(list,root);
//         int[] ret=new int[list.size()];
//         for(int i=0;i<list.size();i++){
//             ret[i]=list.get(i);
//         }
//         return ret;
//     }
// }


// //迭代1
// 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;
//     }
// }




//迭代2
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;
    }
}