Welcome to Subscribe On Youtube

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

897. Increasing Order Search Tree (Easy)

Given the root of a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only one right child.

 

Example 1:

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

Example 2:

Input: root = [5,1,7]
Output: [1,null,5,null,7]

 

Constraints:

• The number of nodes in the given tree will be in the range [1, 100].
• 0 <= Node.val <= 1000

Related Topics:
Tree, Depth-first Search, Recursion

Solution 1. In-order Traversal

// OJ: https://leetcode.com/problems/increasing-order-search-tree
// Time: O(N)
// Space: O(H)
class Solution {
private:
    TreeNode *prev;
    void inorder(TreeNode *root) {
        if (!root) return;
        inorder(root->left);
        root->left = NULL;
        prev->right = root;
        prev = root; 
        inorder(root->right);
    }
public:
    TreeNode* increasingBST(TreeNode* root) {
        TreeNode head;
        prev = &head;
        inorder(root);
        return head.right;
    }
};

Solution 2. Post-order Traversal

// OJ: https://leetcode.com/problems/increasing-order-search-tree/
// Time: O(N)
// Space: O(H)
class Solution {
    pair<TreeNode*, TreeNode*> dfs(TreeNode* root) {
        TreeNode *head = root, *tail = root;
        if (root->left) {
            auto [leftHead, leftTail] = dfs(root->left);
            head = leftHead;
            leftTail->right = root;
            root->left = NULL;
        }
        if (root->right) {
            auto [rightHead, rightTail] = dfs(root->right);
            root->right = rightHead;
            tail = rightTail;
        }
        return { head, tail };
    }
public:
    TreeNode* increasingBST(TreeNode* root) {
        return dfs(root).first;
    }
};

• Java
• C++
• Python
• Go

• /**
   * Definition for a binary tree node.
   * public class TreeNode {
   *     int val;
   *     TreeNode left;
   *     TreeNode right;
   *     TreeNode(int x) { val = x; }
   * }
   */
  class Solution {
      public TreeNode increasingBST(TreeNode root) {
          if (root == null || root.left == null && root.right == null)
              return root;
          List<Integer> inorderTraversal = inorderTraversal(root);
          TreeNode newRoot = new TreeNode(inorderTraversal.get(0));
          TreeNode temp = newRoot;
          int size = inorderTraversal.size();
          for (int i = 1; i < size; i++) {
              TreeNode node = new TreeNode(inorderTraversal.get(i));
              temp.right = node;
              temp = temp.right;
          }
          return newRoot;
      }
  
      public List<Integer> inorderTraversal(TreeNode root) {
          List<Integer> inorderTraversal = new ArrayList<Integer>();
          Stack<TreeNode> stack = new Stack<TreeNode>();
          TreeNode node = root;
          while (!stack.isEmpty() || node != null) {
              while (node != null) {
                  stack.push(node);
                  node = node.left;
              }
              TreeNode visitNode = stack.pop();
              inorderTraversal.add(visitNode.val);
              node = visitNode.right;
          }
          return inorderTraversal;
      }
  }
  
  ############
  
  /**
   * Definition for a binary tree node.
   * public class TreeNode {
   *     int val;
   *     TreeNode left;
   *     TreeNode right;
   *     TreeNode() {}
   *     TreeNode(int val) { this.val = val; }
   *     TreeNode(int val, TreeNode left, TreeNode right) {
   *         this.val = val;
   *         this.left = left;
   *         this.right = right;
   *     }
   * }
   */
  class Solution {
      private TreeNode prev;
      public TreeNode increasingBST(TreeNode root) {
          TreeNode dummy = new TreeNode(0, null, root);
          prev = dummy;
          dfs(root);
          return dummy.right;
      }
  
      private void dfs(TreeNode root) {
          if (root == null) {
              return;
          }
          dfs(root.left);
          prev.right = root;
          root.left = null;
          prev = root;
          dfs(root.right);
      }
  }
  

• // OJ: https://leetcode.com/problems/increasing-order-search-tree
  // Time: O(N)
  // Space: O(H)
  class Solution {
      TreeNode *prev = nullptr;
  public:
      TreeNode* increasingBST(TreeNode* root) {
          if (!root) return nullptr;
          auto head = increasingBST(root->left);
          root->left = nullptr;
          if (prev) prev->right = root;
          prev = root;
          root->right = increasingBST(root->right);
          return head ? head : root;
      }
  };
  

• # Definition for a binary tree node.
  # class TreeNode:
  #     def __init__(self, val=0, left=None, right=None):
  #         self.val = val
  #         self.left = left
  #         self.right = right
  class Solution:
      def increasingBST(self, root: TreeNode) -> TreeNode:
          def dfs(root):
              if root is None:
                  return
              nonlocal prev
              dfs(root.left)
              prev.right = root
              root.left = None
              prev = root
              dfs(root.right)
  
          dummy = TreeNode(val=0, right=root)
          prev = dummy
          dfs(root)
          return dummy.right
  
  ############
  
  # Definition for a binary tree node.
  # class TreeNode(object):
  #     def __init__(self, x):
  #         self.val = x
  #         self.left = None
  #         self.right = None
  
  class Solution(object):
      def increasingBST(self, root):
          """
          :type root: TreeNode
          :rtype: TreeNode
          """
          array = self.inOrder(root)
          if not array:
              return None
          newRoot = TreeNode(array[0])
          curr = newRoot
          for i in range(1, len(array)):
              curr.right =TreeNode(array[i])
              curr = curr.right
          return newRoot
          
      def inOrder(self, root):
          if not root:
              return []
          array = []
          array.extend(self.inOrder(root.left))
          array.append(root.val)
          array.extend(self.inOrder(root.right))
          return array
  

• /**
   * Definition for a binary tree node.
   * type TreeNode struct {
   *     Val int
   *     Left *TreeNode
   *     Right *TreeNode
   * }
   */
  func increasingBST(root *TreeNode) *TreeNode {
  	dummy := &TreeNode{Val: 0, Right: root}
  	prev := dummy
  	var dfs func(root *TreeNode)
  	dfs = func(root *TreeNode) {
  		if root == nil {
  			return
  		}
  		dfs(root.Left)
  		prev.Right = root
  		root.Left = nil
  		prev = root
  		dfs(root.Right)
  	}
  	dfs(root)
  	return dummy.Right
  }
  

All Problems

All Solutions