Leetcode题解（32）

107. Binary Tree Level Order Traversal II

题目

直接代码：

 1 /**
 2  * Definition for a binary tree node.
 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     vector<vector<int>> levelOrderBottom(TreeNode* root) {
13        vector<vector<int>> res;
14        vector<int> temp;
15        if(NULL == root)
16            return res;
17 
18        queue<TreeNode*> myQue;
19        TreeNode *temp1;
20        bool flag = true;
21        myQue.push(root);
22       
23        while (!myQue.empty())
24        {
25            temp.clear();
26            myQue.push(NULL);
27            temp1 = myQue.front();
28            myQue.pop();
29            while (NULL != temp1)
30            {
31                temp.push_back(temp1->val);
32                if(NULL != temp1->left)
33                    myQue.push(temp1->left);
34                if(NULL != temp1->right)
35                    myQue.push(temp1->right);
36                temp1 = myQue.front();
37                myQue.pop();
38            }
39           
40 
41            res.push_back(temp);
42        }
43        reverse(res.begin(),res.end());
44        return res;
45     }
46     
47 };

-----------------------------------------------------------------------------------------分割线----------------------------------------------------------------------------

108. Convert Sorted Array to Binary Search Tree

题目

分析：

讲一个排好序的数组，构造成平衡二叉树，并且是二叉搜索树，其基本思想是折半（二分）法。

代码如下：

 1 /**
 2  * Definition for a binary tree node.
 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>& nums) {
13         int size = nums.size();
14         if(0 == size)
15             return NULL;
16         TreeNode *root = mySortedArrayToBST(nums,0,size-1);
17         return root;
18     }
19     TreeNode* mySortedArrayToBST(vector<int>& nums,int start,int end)
20     {
21         int middle = (start+end)/2;
22         TreeNode *temp = new TreeNode(nums[middle]);
23         if(middle == start)
24             temp->left = NULL;
25         else
26             temp->left = mySortedArrayToBST(nums,start,middle-1);
27         
28         if(middle == end)
29             temp->right = NULL;
30         else
31             temp->right = mySortedArrayToBST(nums,middle+1,end);
32         
33         return temp;
34     }
35 };