二叉树系列 - 二叉搜索树 - 线性时间内把有序链表转化为BST

时间：2024-11-20 21:07:08

引言

本文来自于Google的一道题目：

how to merge two binary search tree into balanced binary search tree. how to merge two binary search tree into balanced binary search tree.. Let there be m elements in first tree and n elements in the other tree. Your merge function should take O(m+n) time and do it in place.

http://www.careercup.com/question?id=5261732222074880

要线性时间内完成，而且要求in place，不难想到把BST转换为Double linked list。

然后将两个dll merge。但是，存在线性时间复杂度的算法，把dll转化成BST吗？

下面就是本文要记述的内容，算法参考自

http://www.geeksforgeeks.org/in-place-conversion-of-sorted-dll-to-balanced-bst/

已排序的 Double linked list 转化为 BST

因为要求线性时间，所以必须保证DLL上的每个节点只被访问 consant 次，最好是一次。

既然要求每个节点只能被访问一次，那么从根节点构造肯定是不行的。这种算法让BST从叶节点开始被构造，通过灵活地运用递归，巧妙地实现了自底向上构造BST的过程，而且还能保证BST是平衡的。

#include<iostream>

#include<stack>

using namespace std;

struct BSTNode{

    int val;

    BSTNode *left;

    BSTNode *right;

    BSTNode(int v): val(v), left(NULL), right(NULL){}

};

class BSTtoDLL{

    public:

        BSTNode *func(BSTNode *root){

            BSTtoDLLCore(root);

            return head;

        }

    private:

        BSTNode* pre = NULL;

        BSTNode* head = NULL;

        void BSTtoDLLCore(BSTNode *root){

            if(!root) return;

            BSTtoDLLCore(root -> left);

            if(pre){

                pre -> right = root;

                root -> left = pre;

            }else{

                head = root;

            }

            pre = root;

            BSTtoDLLCore(root -> right);

        }

};

class DLLtoBalancedBST{

    public:

        BSTNode* func(BSTNode* head){

            if(!head) return head;

            int n = ;

            for(BSTNode *p = head; p; ++n, p = p -> right);

            return DLLtoBalancedBSTCore(&head, n);

        }

    private:

        //DLL to BST in place, Time O(N), Space O(LogN) for stack, N is the amount of nodes.

        //DLL needs to be sorted.

        BSTNode* DLLtoBalancedBSTCore(BSTNode** headref, int n){

            if(n == ) return NULL;

            BSTNode* left = DLLtoBalancedBSTCore(headref, n/);

            BSTNode *root = *headref;

            root -> left = left;

            *headref = root -> right;

            root -> right = DLLtoBalancedBSTCore(headref, n-n/-);

            return root;

        }

};

void InorderPrint(BSTNode* root){

    if(!root) return;

    stack<BSTNode *> st;

    while(!st.empty() || root){

        if(!root){

            root = st.top();

            st.pop();

            cout << root -> val << ' ';

            root = root -> right;

        }else{

            st.push(root);

            root = root -> left;

        }

    }

    cout << endl;

}

int main(){

    //Construct oringal BST

    BSTNode *root = new BSTNode();

    BSTNode *left3 = new BSTNode();

    BSTNode *left1 = new BSTNode();

    BSTNode *left2 = new BSTNode();

    BSTNode *right6 = new BSTNode();

    BSTNode *right7 = new BSTNode();

    root -> left = left2;

    left2 -> left = left1;

    left2 -> right = left3;

    root -> right = right7;

    right7 -> left = right6;

    cout << "-------Inorder print BST-------\n";

    InorderPrint(root);

    //Convert BST to DLL

    BSTtoDLL bstdll;

    BSTNode *head = bstdll.func(root);

    BSTNode *p = head;

    cout << "-------print converted double linked list----------\n";

    for(; p->right != NULL; cout << p -> val << ' ', p = p -> right);

    cout << endl;

    for(; p != NULL; cout << p -> val << ' ', p = p -> left);

    cout << endl;

    //Convert DLL back to Balenced BST

    DLLtoBalancedBST dllbst;

    BSTNode *con_root = dllbst.func(head);

    cout << "-------Inorder print converted BST-------\n";

    InorderPrint(con_root);

    return ;

}

高亮部分为转化过程。

每次递归，headaddr这个指向节点的指针向末尾移动一次。因此每个节点只被访问一次，时间复杂度是线性的。

我们可以发现，这种算法对单向链表也适用。当然单链表不能保证in place，必须新申明节点，但是时间复杂度依然是线性的。

下面给出单向链表上的实现。

已排序的单向Linked list 转化为BST

#include<iostream>

#include<stack>

using namespace std;

struct ListNode{

    int val;

    ListNode* next;

    ListNode(int v): val(v), next(NULL){}

};

struct BSTnode{

    int val;

    BSTnode* left;

    BSTnode* right;

    BSTnode(int v): val(v), left(NULL), right(NULL){}

};

BSTnode *LLtoBSTCore(ListNode **headaddr, int n){

    if(n <= ) return NULL;

    BSTnode *left = LLtoBSTCore(headaddr, n/);

    BSTnode *root = new BSTnode((*headaddr) -> val);

    root -> left = left;

    *headaddr = (*headaddr) -> next;

    root -> right = LLtoBSTCore(headaddr, n-n/-);

    return root;

}

BSTnode *LLtoBST(ListNode *head){

    if(!head) return NULL;

    int n = ; ListNode *p = head;

    for(; p; ++n, p = p -> next);

    return LLtoBSTCore(&head, n);

}

int main(){

    ListNode *head = new ListNode();

    ListNode *end = head;

    for(int i = ; i <= ; end -> next = new ListNode(i++), end = end -> next);

    cout << "List: \n";

    for(ListNode *p = head; p; cout << p -> val << ' ', p = p -> next);

    cout << endl;

    BSTnode *root = LLtoBST(head);

    cout << "BST inorder: " << endl;

    stack<BSTnode *> st;

    while(!st.empty() || root){

        if(!root){

            root = st.top();

            st.pop();

            cout << root -> val << " ";

            root = root -> right;

        }else{

            st.push(root);

            root = root -> left;

        }

    }

    cout << endl;

}

高亮部分为转化过程。

给一个已排序的序列的 Iterator，将序列转化为BST

再推而广之，对于给定一个只能向 next 移动的iterator，通过这个算法也能构造将 iterator 经过的节点构造为BST。不过我们事先知道或者计算出序列的长度。

这里给出C#的实现代码。IEnumerator 就是一个迭代器，支持MoveNext() - 将迭代器往后移，Current 属性 - 返回迭代器当前所指向的值。

高亮部分为基于IEnumrator的构造过程。

因为接口IEnumerator 不是.NET CLR 中的 primitive type(基元类型)，因此将 IEnumerator 赋值或者作为函数参数时，都是按引用传递，这正是我们需要的。因此C#的实现代码省去了C++中使用 两个**的麻烦。

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace ConsoleApplication1

{

    public class BSTNode<T>

    {

        public T val;

        public BSTNode<T> left;

        public BSTNode<T> right;

        public BSTNode(T v)

        {

            val = v;

            left = null;

            right = null;

        }

    }

    /// <summary>

    /// Build Binary search tree from given iterator

    /// </summary>

    public class BuildBST

    {

        public BSTNode<T> BuildFromIEt<T>(IEnumerator<T> it, int n)

        {

            if (n == ) return null;

            BSTNode<T> left = BuildFromIEt(it, n / );

            it.MoveNext();

            BSTNode<T> node = new BSTNode<T>(it.Current);

            node.left = left;

            node.right = BuildFromIEt(it, n - n /  - );

            return node;

        }

    }

    /// <summary>

    /// A class to out put nodes in a tree

    /// </summary>

    public class TreeTrav

    {

        public static void Inorde<T>(BSTNode<T> root)

        {

            if (root == null) return;

            Stack<BSTNode<T>> st = new Stack<BSTNode<T>>();

            while (root != null || st.Count > )

            {

                if (root == null)

                {

                    root = st.Peek();

                    st.Pop();

                    Console.Write(root.val.ToString() + ' ');

                    root = root.right;

                }

                else

                {

                    st.Push(root);

                    root = root.left;

                }

            }

            Console.WriteLine();

        }

    }

    class Program

    {

        static void Main(string[] args)

        {

            IEnumerable<int> list = new List<int>() { , , , , ,  };

            Console.WriteLine("----Original list----");

            for (IEnumerator<int> it = list.GetEnumerator(); it.MoveNext(); Console.Write(it.Current.ToString() + ' ')) ;

            Console.WriteLine();

            BuildBST buildBST = new BuildBST();

            BSTNode<int> root = buildBST.BuildFromIEt(list.GetEnumerator(), list.Count());

            Console.WriteLine("----Inorder traverse generated BST----");

            TreeTrav.Inorde(root);

            Console.Read();

        }

    }

}

相关文章