In-place Java Solution (With Detail Explanation)


  • 2
    S

    In order to do it in place, no stack or queue or recursive calls are allowed. Then, the only thing I can use is the tree structure itself.

    Firstly, I want to traversal to the very most left TreeNode, and then put it in between of itself parent TreeNode and right brother TreeNode. That gives me a problem:

    I need something to store its parent, and to work for each very most left TreeNode, I need to store each parent I meet, which leads to stack. That's extra space.

    Thus, I cannot traversal until very most, neither can I traversal away from the main root node. Each time my TreeNode pointer is away from root node, I need to make sure the root node is fine to go.

    That leads me to a second trial. Always going down the right branch, when a node has a left branch, put the left branch in between of itself and its right branch.

    public class Solution {
        public void flatten(TreeNode root) {
            TreeNode head = new TreeNode(0);
            head.right = root;
            TreeNode node = head;
            while(node.right!=null){
                node = node.right;
                if(node.left!=null){
                    TreeNode end = node.left;
                    while(end.right!=null){
                        end = end.right;
                    }
                    TreeNode temp = node.right;
                    node.right = node.left;
                    node.left = null;
                    end.right = temp;
                }
            }
            head.right = null;
        }
    }

Log in to reply
 

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