In-place Java Solution (With Detail Explanation)

  • 2

    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;
                node = node.right;
                    TreeNode end = node.left;
                        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.