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

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

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

推荐阅读：
夏季炒菜时可多放一种调料——花椒　 四种热门食物并没有那么神奇的营养功效　 “养胃饼干”不养胃 消费者起诉徐静蕾代言　 盛夏常饮枸杞菊花茶 保养眼睛功效强　 西瓜虽好，但这九类人群不宜吃西瓜　 保健酒乱象调查：为见效快违法添加伟哥　 饮用蜂蜜水的最佳时间及注意事项　 红枣维生素含量高 喝大枣水养肝排毒　 黑木耳营养丰富对健康有五大好处　 香蕉和橘子能起到解毒护肝的作用　
评论列表
添加评论