首页 > 代码库 > Convert Sorted Array to Binary Search Tree & Convert Sorted List to Binary Search Tree

Convert Sorted Array to Binary Search Tree & Convert Sorted List to Binary Search Tree

2024-07-19 21:47:14   223人阅读

Convert Sorted Array to Binary Search Tree

 

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

 

方法：将有序数组转为平衡二叉树，我们知道平衡二叉树的中序遍历是有序数组，而且“中间”的元素可以作为根节点，那么构建树的时候，找出中间元素，构造根元素，然后继续重复上面的方法，构造左子树和右子树。代码如下：

 1 /** 2  * Definition for binary tree 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     TreeNode *sortedArrayToBST(vector<int> &num) {13         TreeNode* root = 0;14         constructBST(num, 0, num.size()-1, root);15         return root;16     }17     18     void constructBST(vector<int>& num, int ibegin, int iend, TreeNode*& root) {    //root是引用19         if(ibegin > iend) return;20         int mid = ibegin + (iend-ibegin)/2; //取中间的元素21         root = new TreeNode(num[mid]);  //建立根节点22         constructBST(num, ibegin, mid-1, root->left);   //构建左子树23         constructBST(num, mid+1, iend, root->right);    //构建右子树24     }25 };

Convert Sorted List to Binary Search Tree

 

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

 

方法同上，不过这次是单链表不是数组，那么可以设置快慢指针，快指针每次走两步，慢指针每次走一步，找出中间节点，继而构造根节点，继续上面的步骤，构造左子树和右子树，代码如下：
 1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     ListNode *next; 6  *     ListNode(int x) : val(x), next(NULL) {} 7  * }; 8  */ 9 /**10  * Definition for binary tree11  * struct TreeNode {12  *     int val;13  *     TreeNode *left;14  *     TreeNode *right;15  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}16  * };17  */18 class Solution {19 public:20     TreeNode *sortedListToBST(ListNode *head) {21         TreeNode* root = 0;22         constructBST(head, root);23         return root;24     }25     26     void constructBST(ListNode* head, TreeNode*& root) {27         if( !head ) return ;    //如果链表为空，则说明子树为空28         ListNode* pre = 0;  //slow的前驱节点29         ListNode* fast = head;  //快指针，每次走两步30         ListNode* slow = head;  //慢指针，每次走一步31         while( fast && fast->next ) {32             fast = fast->next->next;33             pre = slow;34             slow = slow->next;35         }36         ListNode* lhead = 0;        //新左链表37         ListNode* rhead = slow->next;   //新右链表38         ListNode* midNode = slow;       //中间节点39         midNode->next = 0;40         if( pre ) {    //如果新左链表不为空的情况41             lhead = head;42             pre->next = 0;43         }44         root = new TreeNode(midNode->val);  //利用中间元素构建根节点45         delete midNode;46         constructBST(lhead, root->left);    //构建左子树47         constructBST(rhead, root->right);   //构建右子树48     }49 };

 

 

 

Convert Sorted Array to Binary Search Tree & Convert Sorted List to Binary Search Tree


联系
我们