文章目录
problem Ⅰ
108. Convert Sorted Array to Binary Search Tree
Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.
A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.
Example 1:
Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:
Example 2:
Input: nums = [1,3]
Output: [3,1]
Explanation: [1,3] and [3,1] are both a height-balanced BSTs.
my solution
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* rec(vector<int>& nums, int low, int high){
if(low <= high){
int mid = low + (high-low)/2;// in case of overflow
TreeNode *root = new TreeNode(nums[mid]);
root->left = rec(nums, low, mid-1);
root->right = rec(nums, mid+1, high);
return root;
}
return NULL;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
return rec(nums, 0, nums.size()-1);
}
};
problem Ⅱ
105. Construct Binary Tree from Preorder and Inorder Traversal
Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.
Example 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
Example 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]
my solution 1 brute force
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int preorderIndex = 0;
TreeNode* rec(vector<int>& preorder, vector<int>& inorder, int low, int high){
if(low > high)return NULL;
TreeNode *root = new TreeNode(preorder[preorderIndex++]);
int InorderPos;
for(int i=low; i<=high; i++){
if(inorder[i] == root->val){
InorderPos = i;
break;
}
}
root->left = rec(preorder, inorder, low, InorderPos-1);
root->right = rec(preorder, inorder, InorderPos+1, high);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return rec(preorder, inorder, 0, preorder.size()-1);
}
};
my solution 2 hashmap
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int preorderIndex = 0;
unordered_map<int, int> hashmap;
TreeNode* rec(vector<int>& preorder, vector<int>& inorder, int low, int high){
if(low > high)return NULL;
TreeNode *root = new TreeNode(preorder[preorderIndex++]);
int InorderPos = hashmap[root->val];
root->left = rec(preorder, inorder, low, InorderPos-1);
root->right = rec(preorder, inorder, InorderPos+1, high);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
for(int i=0; i<inorder.size(); i++)
hashmap.insert({inorder[i], i});
return rec(preorder, inorder, 0, preorder.size()-1);
}
};
NOTE:
we can observe that using hashmap is faster but more space use
problem Ⅲ
103. Binary Tree Zigzag Level Order Traversal
Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between).
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]
Example 2:
Input: root = [1]
Output: [[1]]
Example 3:
Input: root = []
Output: []
my solution 1 use stack to reverse
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
int cnt = 1;
queue<TreeNode*> que;
vector<vector<int>> res;
stack<TreeNode*> stk;
que.push(root);
while(!que.empty()){
int size = que.size();
vector<int> tmp;
if(cnt%2==1){
for(int i=0; i<size; i++){
TreeNode *node = que.front();
if(node != NULL){
tmp.push_back(node->val);
que.push(node->left);
que.push(node->right);
}
que.pop();
}
}else{
for(int i=0; i<size; i++){
TreeNode *node = que.front();
if(node != NULL){
stk.push(node);
que.push(node->left);
que.push(node->right);
}
que.pop();
}
while(!stk.empty()){
tmp.push_back(stk.top()->val);
stk.pop();
}
}
if(tmp.size() != 0)res.push_back(tmp);
cnt++;
}
return res;
}
};
time complexity :
O
(
n
)
O(n)
O(n)space complexity :
O
(
n
)
O(n)
O(n)
my solution 2 use reverse() instead of using stack
faster and less space use
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
bool flag = false;
queue<TreeNode*> que;
vector<vector<int>> res;
if(!root)return res;
que.push(root);
while(!que.empty()){
int size = que.size();
vector<int> tmp;
for(; size>0; size--){
TreeNode *node = que.front();
que.pop();
if(node->left)que.push(node->left);
if(node->right)que.push(node->right);
tmp.push_back(node->val);
}
if(flag)reverse(tmp.begin(), tmp.end());
res.push_back(tmp);
flag = !flag;
}
return res;
}
};
time complexity :
O
(
n
)
O(n)
O(n)space complexity :
O
(
n
)
O(n)
O(n)