Iterative solution in Java (Is this a good approach ? It gets accepted)


  • 0
    C

    So my ideas is that inorder will always print the leaf first so..
    I iterate through and push nodes back to stack in reverse order (right first, then itself, then left).
    Then because the node is visited already, so I make it to be leaf by removing its pointer to left and right before re-pushing it back to the stack.
    Whenever stack pop a leaf or node (with left and right pointers null), I will add it into List.

    public class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            ArrayList<Integer> ans = new ArrayList<Integer>();
            Stack <TreeNode> stk = new Stack<TreeNode>();
            if(root == null)return ans;
            stk.push(root);
            while(!stk.isEmpty()){
                TreeNode t = stk.pop();
                if(t.left == null && t.right == null){
                    ans.add(t.val);
                }else{
                    if(t.right != null)stk.push(t.right);
                    stk.push(t);
                    if(t.left != null)stk.push(t.left);
                    t.left = null;
                    t.right = null;
    
                }
            }
            return ans;
        }
    }
    

Log in to reply
 

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