1.树概念:
暂略。
2.树的相关题目:
/**
* 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:
int maxDepth(TreeNode* root) {
if(!root)
{
return 0;
}
if(!root->left && !root->right)//如果根没有孩子了
{
return 1;
}
else
{
int lHeight = maxDepth(root->left);
int rHeight = maxDepth(root->right);
return max(lHeight,rHeight) + 1;
}
}
};
/**
* 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* sortedArrayToBST(vector<int>& nums) {
if(nums.empty())
{
return NULL;
}
return sorted(nums,0,nums.size()-1);
}
TreeNode* sorted(vector<int> nums, int start, int end)
{
if(start > end)
{
return NULL;
}
else if(start == end)
{
TreeNode* tmp = new TreeNode(nums[start]);
return tmp;
}
else
{
int curr = start + (end - start) / 2;
TreeNode* tmp = new TreeNode(nums[curr]);
tmp->left = sorted(nums, start, curr - 1);
tmp->right = sorted(nums, curr + 1, end);
return tmp;
}
}
};
/**
* 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:
bool isSymmetric(TreeNode* root) {
if(!root || (!root->left)&&(!root->right))
{
return true;
}
if(!root->left || !root->right)
{
return false;
}
TreeNode* left_tmp;
TreeNode* right_tmp;
queue<TreeNode*> left_nodes;
queue<TreeNode*> right_nodes;
left_nodes.push(root->left);
right_nodes.push(root->right);
while(!left_nodes.empty() && !right_nodes.empty())
{
left_tmp = left_nodes.front();
right_tmp = right_nodes.front();
if(left_tmp->val == right_tmp->val)
{
if((!left_tmp->left && right_tmp->right) || (left_tmp->left && !right_tmp->right))
{
break;
}
else if(left_tmp->left && right_tmp->right)
{
left_nodes.push(left_tmp->left);
right_nodes.push(right_tmp->right);
}
if((!left_tmp->right && right_tmp->left) || (left_tmp->right && !right_tmp->left))
{
break;
}
else if(left_tmp->right && right_tmp->left)
{
left_nodes.push(left_tmp->right);
right_nodes.push(right_tmp->left);
}
left_nodes.pop();
right_nodes.pop();
}
else
{
break;
}
}
if(left_nodes.empty() && right_nodes.empty())
{
return true;
}
return false;
}
};
递归解决:
/**
* 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:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
inorder(root,result);
return result;
}
void inorder(TreeNode* root, vector<int> &result)
{
if(root != NULL)
{
inorder(root->left,result);
result.push_back(root->val);
inorder(root->right,result);
}
}
};
栈解决(其实思路和递归一样):
/**
* 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:
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> toTraversal;
vector<int> result;
while(root != NULL || !toTraversal.empty())
{
//遍历左节点
while(root != NULL)
{
toTraversal.push(root);
root = root->left;
}
root = toTraversal.top();
result.push_back(root->val);
toTraversal.pop();
root = root->right;
}
return result;
}
};
递归:
/**
* 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:
int kthSmallest(TreeNode* root, int k) {
vector<int> list;
findKth(root,k,list);
return list[k-1];
}
void findKth(TreeNode* root,int k,vector<int> &list)
{
if(root != NULL)
{
findKth(root->left,k,list);
list.push_back(root->val);
if(list.size() == k)
{
return;
}
findKth(root->right,k,list);
}
}
};
迭代:
/**
* 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:
int kthSmallest(TreeNode* root, int k) {
vector<int> res;
stack<TreeNode*> ss;
TreeNode* top;
while(root || !ss.empty())
{
while(root)
{
ss.push(root);
root = root->left;
}
root = ss.top();
res.push_back(root->val);
ss.pop();
if(res.size() == k)
{
break;
}
root = root->right;
}
return res[k-1];
}
};
/**
* 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* buildTree(vector<int>& preorder, vector<int>& inorder) {
int pos = 0;
return build(preorder, inorder, 0, inorder.size(),pos);
}
TreeNode* build(vector<int> &preorder, vector<int> &inorder,int begin,int end,int &pos)
{
if(begin>=end || pos >= preorder.size() )
{
return NULL;
}
TreeNode *root = new TreeNode(preorder[pos++]);
int cur = begin;
while(root->val != inorder[cur])
{
cur++;
}
root->left = build(preorder, inorder, begin, cur, pos);
root->right = build(preorder, inorder, cur+1, end, pos);
return root;
}
};
/**
* 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:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if(!root)
{
return res;
}
vector<int> tmp;
queue<TreeNode*> odd;
queue<TreeNode*> even;
even.push(root);
tmp.push_back(root->val);
res.push_back(tmp);
int count = 1;
while(!even.empty() || !odd.empty())
{
vector<int> tmp;
if(count % 2 == 0)
{
while(!odd.empty())
{
if(odd.front()->left)
{
even.push(odd.front()->left);
tmp.push_back(odd.front()->left->val);
}
if(odd.front()->right)
{
even.push(odd.front()->right);
tmp.push_back(odd.front()->right->val);
}
odd.pop();
}
if(tmp.size())
{
res.push_back(tmp);
}
count++;
}
else
{
while(!even.empty())
{
if(even.front()->left)
{
odd.push(even.front()->left);
tmp.push_back(even.front()->left->val);
}
if(even.front()->right)
{
odd.push(even.front()->right);
tmp.push_back(even.front()->right->val);
}
even.pop();
}
if(tmp.size())
{
res.push_back(tmp);
}
count++;
}
}
return res;
}
};
/**
* 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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
find(root , p, q);
return ans;
}
bool find(TreeNode* root, TreeNode* p, TreeNode * q)
{
if(root == NULL)
{
return false;
}
bool left = find(root->left, p, q) ? 1 : 0;
bool right = find(root->right, p, q) ? 1 : 0;
bool mid = (root == p || root == q) ? 1 : 0;
if(left+right+mid > 1 && !ans)
{
ans = root;
}
return left+right+mid;
}
private: TreeNode* ans;
};
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;
Node() {}
Node(int _val, Node* _left, Node* _right, Node* _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution {
public:
Node* connect(Node* root) {
if(!root) return NULL;
queue<Node*> odd;
queue<Node*> even;
int layer = 0;
even.push(root);
Node* tmp;
while(!odd.empty() || !even.empty())
{
while((layer + 1) % 2 && !even.empty()) //下一层为奇数层
{
tmp = even.front();
if(tmp->left) odd.push(tmp->left);
if(tmp->right) odd.push(tmp->right);
even.pop();
if(!even.empty()) tmp->next = even.front();
else
{
layer++;
continue;
}
}
while((layer + 1) % 2 == 0 && !odd.empty())
{
tmp = odd.front();
if(tmp->left) even.push(tmp->left);
if(tmp->right) even.push(tmp->right);
odd.pop();
if(!odd.empty()) tmp->next = odd.front();
else
{
layer++;
continue;
}
}
}
return root;
}
};
/**
* 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:
bool isValidBST(TreeNode* root) {
return isValid(root, NULL, NULL);
}
bool isValid(TreeNode* root, TreeNode* upper, TreeNode* lowwer){
if(!root)
{
return true;
}
if(upper && root->val >= upper->val) return false;
if(lowwer && root->val <= lowwer->val) return false;
if(!isValid(root->left, root, lowwer)) return false;
if(!isValid(root->right,upper, root)) return false;
return true;
}
};
/**
* 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* mergeTrees(TreeNode* t1, TreeNode* t2) {
if(!t1 && !t2)
{
return NULL;
}
if(!t1 && t2)
{
return t2;
}
if(t1 && !t2)
{
return t1;
}
t1->val += t2->val;
t1->left = mergeTrees(t1->left, t2->left);
t1->right = mergeTrees(t1->right, t2->right);
return t1;
}
};
/**
* 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* invertTree(TreeNode* root) {
if(!root)
{
return NULL;
}
TreeNode* tmp = root->left;
root->left = invertTree(root->right);
root->right = invertTree(tmp);
return root;
}
};