二叉树的先序遍历

144. 二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,2,3]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[1,2]

示例 5：

输入：root = [1,null,2]
输出：[1,2]

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

代码

class Solution {
    List<Integer> list = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        //  preorder01(root);
        //  preorder02(root);
        preorder03(root);
        return list;
    }


    //递归
    public void preorder01(TreeNode root){
        if(root==null) return;
        list.add(root.val);
        preorder01(root.left);
        preorder01(root.right);
    }    
    

    //迭代
    public void preorder02(TreeNode root){
        if(root==null) return;
        Stack<TreeNode> st = new Stack<>();
        while(root!=null||!st.isEmpty()){
            while(root!=null){
                list.add(root.val);
                st.push(root);
                root = root.left;
            }
            TreeNode node = st.pop();
            if(node.right  != null){
                root = node.right;
            }
        }
    }

    //迭代, Morris遍历,入栈顺序中右左
    public void preorder03(TreeNode root){
        if(root==null) return;
        Stack<TreeNode> st = new Stack<>();
        st.push(root);
        while(!st.isEmpty()){
            root = st.pop(); //中
            list.add(root.val);
            if(root.right!=null){ //右
                st.push(root.right);
            }
            if(root.left!=null){ //左
                st.push(root.left);
            }
        }
    }

    //迭代标记法
    public void preorder04(TreeNode root){
        if(root==null) return;
         Stack<TreeNode> st = new Stack<>();
         st.push(root);
         while(!st.isEmpty()){
             root = st.pop();
             if(root!=null){
                 if(root.right!=null) st.push(root.right); //右
                 if(root.left!=null) st.push(root.left); //左
                 st.push(root); //中
                 st.push(null); //标记
             }else{
                 root = st.pop(); //遇到空结点就访问
                 list.add(root.val);
             }
         }
    }
}