4 java solutions include recursive,morris and two other iterative


  • 2
    Q

    recursive

    List<Integer> l=new ArrayList<Integer>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root==null) return l;
        l.add(root.val);
        if(root.left!=null) preorderTraversal(root.left);
        if(root.right!=null) preorderTraversal(root.right);
        return l;
    }
    

    Morris

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> l=new ArrayList<Integer>();
        if(root==null) return l;
        TreeNode pre,cur=root;
        while(cur!=null){
            if(cur.left==null){
                l.add(cur.val);
                cur=cur.right;
            }else{
                pre=cur.left;
                while(pre.right!=null&&pre.right!=cur){
                    pre=pre.right;
                }
                if(pre.right==null){
                    pre.right=cur;
                    l.add(cur.val);
                    cur=cur.left;
                }else{
                    pre.right=null;
                    cur=cur.right;
                }
            }
        }
        return l;
    }
    

    Iterative1

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> l=new ArrayList<Integer>();
        if(root==null) return l;
        Stack<TreeNode> stack=new Stack<TreeNode>();
        while(!stack.isEmpty()||root!=null){
            if(root!=null){
                l.add(root.val);
                stack.push(root);
                root=root.left;
            }else{
                root=stack.pop();
                root=root.right;
            }
        }
        return l;
    }
    

    Iterative2

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> l=new ArrayList<Integer>();
        if(root==null) return l;
        Stack<TreeNode> stack=new Stack<TreeNode>();
        stack.push(root);
        while(!stack.isEmpty()){
            root=stack.pop();
            l.add(root.val);
            if(root.right!=null) stack.push(root.right);
            if(root.left!=null) stack.push(root.left);
        }
        return l;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.