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

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

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

推荐阅读：
加法原理和乘法原理练习题　 男装与女装　 工程问题：甲乙两人合做12天　 甲乙两商店中某种商品的定价相同　 有甲乙两个书架　 还有一元钱去了哪里了　 孙老师今年36岁，陈天任今年10岁　 小朋友排成一队，从前面数小力排在第10个　 陈叔叔和李阿妹共同得到一笔奖金　 小红看的故事书一共有多少页　
评论列表
添加评论