Welcome to Subscribe On Youtube

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
• C++
• Javascript
• C#
• Python

• /*
  // Definition for a Node.
  class Node {
      public int val;
      public Node left;
      public Node right;
      public Node parent;
  };
  */
  
  class Solution {
      public Node flipBinaryTree(Node root, Node leaf) {
          Node cur = leaf;
          Node p = cur.parent;
          while (cur != root) {
              Node gp = p.parent;
              if (cur.left != null) {
                  cur.right = cur.left;
              }
              cur.left = p;
              p.parent = cur;
              if (p.left == cur) {
                  p.left = null;
              } else if (p.right == cur) {
                  p.right = null;
              }
              cur = p;
              p = gp;
          }
          leaf.parent = null;
          return leaf;
      }
  }
  

• /*
  // Definition for a Node->
  class Node {
  public:
      int val;
      Node* left;
      Node* right;
      Node* parent;
  };
  */
  
  class Solution {
  public:
      Node* flipBinaryTree(Node* root, Node* leaf) {
          Node* cur = leaf;
          Node* p = cur->parent;
          while (cur != root) {
              Node* gp = p->parent;
              if (cur->left) {
                  cur->right = cur->left;
              }
              cur->left = p;
              p->parent = cur;
              if (p->left == cur) {
                  p->left = nullptr;
              } else if (p->right == cur) {
                  p->right = nullptr;
              }
              cur = p;
              p = gp;
          }
          leaf->parent = nullptr;
          return leaf;
      }
  };
  

• /**
   * // Definition for a Node.
   * function Node(val) {
   *    this.val = val;
   *    this.left = null;
   *    this.right = null;
   *    this.parent = null;
   * };
   */
  
  /**
   * @param {Node} node
   * @return {Node}
   */
  var flipBinaryTree = function (root, leaf) {
      let cur = leaf;
      let p = cur.parent;
      while (cur != root) {
          const gp = p.parent;
          if (cur.left != null) {
              cur.right = cur.left;
          }
          cur.left = p;
          p.parent = cur;
          if (p.left == cur) {
              p.left = null;
          } else if (p.right == cur) {
              p.right = null;
          }
          cur = p;
          p = gp;
      }
      leaf.parent = null;
      return leaf;
  };
  
  

• /*
  // Definition for a Node.
  public class Node {
      public int val;
      public Node left;
      public Node right;
      public Node parent;
  }
  */
  
  public class Solution {
      public Node FlipBinaryTree(Node root, Node leaf) {
          Node cur = leaf;
          Node p = cur.parent;
          while (cur != root) {
              Node gp = p.parent;
              if (cur.left != null) {
                  cur.right = cur.left;
              }
              cur.left = p;
              p.parent = cur;
              if (p.left == cur) {
                  p.left = null;
              } else if (p.right == cur) {
                  p.right = null;
              }
              cur = p;
              p = gp;
          }
          leaf.parent = null;
          return leaf;
      }
  }
  

• """
  # Definition for a Node.
  class Node:
      def __init__(self, val):
          self.val = val
          self.left = None
          self.right = None
          self.parent = None
  """
  
  
  class Solution:
      def flipBinaryTree(self, root: "Node", leaf: "Node") -> "Node":
          cur = leaf
          p = cur.parent
          while cur != root:
              gp = p.parent
              if cur.left:
                  cur.right = cur.left
              cur.left = p
              p.parent = cur
              if p.left == cur:
                  p.left = None
              elif p.right == cur:
                  p.right = None
              cur = p
              p = gp
          leaf.parent = None
          return leaf
  
  

All Problems

All Solutions