Accepted Java iterative and recursive solutions


  • 1

    The iterative way to do it is to use a stack, since preorder is basically dfs. Just remember to push the right child and then the left child, which makes the left one come out first.

    The recursive solution is more concise though. here i present both ways to solve this problem.

       public class Solution {
        //first is iterative solution
            public List<Integer> preorderTraversal(TreeNode root) {
                List<Integer> ans = new ArrayList<Integer>();
                if (root==null) return ans;
                Stack<TreeNode> st = new Stack<TreeNode>();
                st.push(root);
                while (!st.isEmpty()){
                    TreeNode curr = st.pop();
                    ans.add(curr.val);
                    if (curr.right!=null) st.push(curr.right);
                    if (curr.left!=null) st.push(curr.left);
                }
                
                return ans;
            }
            
    
        //then recursive
            public List<Integer> preorderTraversal_recur(TreeNode root) {
                List<Integer> ans = new ArrayList<Integer>();
                if (root==null) return ans;
                ans.add(root.val);
                ans.addAll(preorderTraversal_recur(root.left));
                ans.addAll(preorderTraversal_recur(root.right));
                return ans;
            }
        }

Log in to reply
 

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