Java solution, both recursion and iteration


  • 18
    H
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        // method 1: recursion
    
        helper(root, res);
        return res;
    
        //helper function for method 1
        private void helper(TreeNode root, List<Integer> res) {
            if (root != null) {
                if (root.left != null) {
                    helper(root.left, res);
                }
                res.add(root.val);
                if (root.right != null) {
                    helper(root.right, res);
               }
           }
       }
    

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        // method 2: iteration
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            res.add(cur.val);
            cur = cur.right;
        }
        return res;        
    }

  • 12
    D

    your helper can write as

    private void helper(TreeNode root, List<Integer> res) {
    		if (root != null) {
    			helper(root.left, res);
    			res.add(root.val);
    			helper(root.right, res);		
    		}
    	}

Log in to reply
 

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