Share my Java solution using stack


  • 0
    P

    inorder traversal using a stack

    public void flatten(TreeNode root) {
        if(root == null){
            return;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode cur = root;
        helper(root, stack);
    }
    
    public void helper(TreeNode root, Stack<TreeNode> stack){
        if(root == null){
            return;
        }
        
       //if right child is not null, put it in the stack for later use
        if(root.right!=null){
            stack.push(root.right);
        }
        
        //if the left child is null, pop the element from the stack, and do recursion to the right child
        if(root.left == null){
            if(stack.empty()){
                return;
            }
            TreeNode cur = stack.pop();
            root.right = cur;
            helper(root.right, stack);
        }
        
        // if the left child is not null, put it to the right, null the left child, and do recursion to the right child
        if(root.left!=null){
            root.right = root.left;
            root.left = null;
            helper(root.right, stack);
            
        }
        return;
        
    }

Log in to reply
 

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