How to Turn a Binary Search Tree into a Increasing Order Search

  • 时间：2020-10-12 15:39:01
  • 分类：网络文摘
  • 阅读：113 次

Given a 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 1 right child.

Example 1:
Input: [5,3,6,2,4,null,8,1,null,null,null,7,9]

       5
      / \
    3    6
   / \    \
  2   4    8
 /        / \ 
1        7   9

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

 1
  \
   2
    \
     3
      \
       4
        \
         5
          \
           6
            \
             7
              \
               8
                \
                 9

The task is to convert a Binary Search Tree into a Inceasing Order Search Tree – which is a sorted linked list – where the Tree has only right nodes.

DFS/Recursion – Inorder

An in-order traversal of a Binary Search Tree yield a sorted list. We can recursively travel the binary tree using DFS (Depth First Search), visit the left nodes first, then parent node, and the right nodes – which is the in-order traversal. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* increasingBST(TreeNode* root) {
        vector<int> nodes;
        dfs(root, nodes); // store the in-order nodes
        TreeNode *ans = new TreeNode(-1); // dummy root node
        TreeNode *p = ans;
        for (const auto &n: nodes) {
            p->right = new TreeNode(n);
            p = p->right;
        }
        return ans->right;
    }
    
    void dfs(TreeNode* root, vector<int> &nodes) {
        if (root == NULL) return;
        dfs(root->left, nodes);
        nodes.push_back(root->val);
        dfs(root->right, nodes);        
    }
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* increasingBST(TreeNode* root) {
        vector<int> nodes;
        dfs(root, nodes); // store the in-order nodes
        TreeNode *ans = new TreeNode(-1); // dummy root node
        TreeNode *p = ans;
        for (const auto &n: nodes) {
            p->right = new TreeNode(n);
            p = p->right;
        }
        return ans->right;
    }
    
    void dfs(TreeNode* root, vector<int> &nodes) {
        if (root == NULL) return;
        dfs(root->left, nodes);
        nodes.push_back(root->val);
        dfs(root->right, nodes);        
    }
};

As we visit the nodes, we put them in order into a separate list – which is to convert to the linked-list later.

Binary Search Tree Inorder Traversal using Iterative Depth First Search Algorithms

We can replace the recursion with manual stacks. We push the left nodes to the stack at priority, and navigate to the right nodes then.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* increasingBST(TreeNode* root) {
        if (root == NULL) return NULL;
        vector<int> nodes;
        stack<TreeNode*> st;     
        TreeNode *p = root;
        while (st.size() > 0 || p) {         
            while (p) {
                st.push(p);    
                p = p->left;
            }                        
            p = st.top();
            st.pop();
            nodes.push_back(p->val);
            p = p->right;
        }
        TreeNode *ans = new TreeNode(-1);
        p = ans;
        for (const auto &n: nodes) {
            p->right = new TreeNode(n);
            p = p->right;
        }
        return ans->right;        
    }
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* increasingBST(TreeNode* root) {
        if (root == NULL) return NULL;
        vector<int> nodes;
        stack<TreeNode*> st;     
        TreeNode *p = root;
        while (st.size() > 0 || p) {         
            while (p) {
                st.push(p);    
                p = p->left;
            }                        
            p = st.top();
            st.pop();
            nodes.push_back(p->val);
            p = p->right;
        }
        TreeNode *ans = new TreeNode(-1);
        p = ans;
        for (const auto &n: nodes) {
            p->right = new TreeNode(n);
            p = p->right;
        }
        return ans->right;        
    }
};

Both methods run at O(N) time complexity and O(N) space complexity – and clearly the recursion results in a cleaner/concise code.

Rewrite the Node Links

As we walk through the nodes, we can just rewrite the pointers without a second run to convert the sorted list into a Increasing Search Order Tree. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* increasingBST(TreeNode* root) {
        if (root == NULL) return NULL;
        stack<TreeNode*> st;     
        TreeNode *p = root;
        TreeNode *ans = new TreeNode(-1);
        TreeNode *pre = ans;
        while (st.size() > 0 || p) {         
            while (p) {
                st.push(p);    
                p = p->left;
            }                        
            p = st.top();
            st.pop();
            p->left = NULL;
            pre->right = p;
            pre = p;
            p = p->right;
        }        
        return ans->right;        
    }
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* increasingBST(TreeNode* root) {
        if (root == NULL) return NULL;
        stack<TreeNode*> st;     
        TreeNode *p = root;
        TreeNode *ans = new TreeNode(-1);
        TreeNode *pre = ans;
        while (st.size() > 0 || p) {         
            while (p) {
                st.push(p);    
                p = p->left;
            }                        
            p = st.top();
            st.pop();
            p->left = NULL;
            pre->right = p;
            pre = p;
            p = p->right;
        }        
        return ans->right;        
    }
};

This approach still runs at O(N) time and space complexity – as it still requires a stack.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
The Minimum Absolute Difference Algorithm of an Array　 Implement the Depth First Search Algorithm in Graph using Simple　 Beginner’s Introduction to PHP Memcached　 Using the Regular Expression to Replace External Links in WordPr　 5 Smart Guides In Taking The Best Hosting Provider　 Checking Subtree of Another Tree using Preorder Traversal or Rec　 How to Optimize WordPress Website for Speed?　 How to Compute the Day of the Week using C++?　 Counting Substrings with Only One Distinct Letter with Different　 Ukranian Authorities Prevent Security Blogger From Getting Kidna　
评论列表
添加评论