Question

Formatted question description: https://leetcode.ca/all/1666.html

 1666. Change the Root of a Binary Tree

 Given the root of a binary tree and a leaf node, reroot the tree so that the leaf is the new root.

 You can reroot the tree with the following steps for each node cur on the path starting from the leaf up to the root​​​ excluding the root:

 If cur has a left child, then that child becomes cur's right child. Note that it is guaranteed that cur will have at most one child.
 cur's original parent becomes cur's left child.
 Return the new root of the rerooted tree.

 Note: Ensure that your solution sets the Node.parent pointers correctly after rerooting or you will receive "Wrong Answer".


 Example 1:


 Input: root = [3,5,1,6,2,0,8,null,null,7,4], leaf = 7
 Output: [7,2,null,5,4,3,6,null,null,null,1,null,null,0,8]


 Example 2:

 Input: root = [3,5,1,6,2,0,8,null,null,7,4], leaf = 0
 Output: [0,1,null,3,8,5,null,null,null,6,2,null,null,7,4]


 Constraints:
     The number of nodes in the tree is in the range [2, 100].
     -109 <= Node.val <= 109
     All Node.val are unique.
     leaf exist in the tree.

Algorithm

The dfs process of this question should actually go from leaf up to root. For each node, we need to change its left, right and parent. node->parent should point to the predecessor node of node (that is, the child on the leaf->root path). node->left should point to the upward path (that is, the original parent). node->right should point to its other child (that is, the child on the non-leaf->root path). Then recursively process the next node on the leaf->root path.

Another pitfall of this question is that the question requires the handling of root, which is slightly different from the handling of other nodes. Just point node->parent to the predecessor node, and then set the child on the leaf->root path to NULL. It is not necessary to migrate the child on the non-path to the right node.

Code

Java

public class Change_the_Root_of_a_Binary_Tree {

    public class Solution {

        public Node flipBinaryTree(Node root, Node leaf) {
            Node curr = leaf;
            Node newParent = null;

            while (curr != root) {

                if (curr.left != null) curr.right = curr.left;

                if (curr.parent != null) {
                    curr.left = curr.parent;


                    if (curr.parent.left == curr) curr.parent.left = null; // cut cycle
                    else curr.parent.right = null; // curr.parent.right == curr , also cut cycle
                }

                // Next
                curr.parent = newParent;
                newParent = curr;
                curr = curr.left; // no need for right, since right is from previusly left child
            }

            // @note: final check
            curr.parent = newParent;

            return leaf;
        }

        class Node {
            public int val;
            public Node left;
            public Node right;
            public Node parent;
        }

    }

}

All Problems

All Solutions