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

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

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) —

推荐阅读：
宣称“高钙”的食品补钙效果未必好　 广告中的“高膳食纤维”食品并不健康　 宣传的“零热量”饮品真的很不靠谱　 宣称健康的“全谷物”饮品营养仅一般　 国家食品药品监督管理总局正式挂牌　 办公室白领防电脑辐射食品大盘点　 春分节气饮食养生不同体质的食疗　 问题奶粉不断涌现，奶粉监管怎么了？　 保健食品营销骗局令人深恶痛绝　 清明时节，可适当多吃寒性食物　
评论列表
添加评论