leetcode中關於樹的題目匯總，這部分題目比較多：
Balanced Binary Tree
[cpp] class Solution {
public:
int subBal(TreeNode* root){
if(root==NULL)
return 0;
int left = subBal(root->left);
int right = subBal(root->right);
if(left<0||right<0||abs(left-right)>1) return -1;
return max(left,right)+1;
}
bool isBalanced(TreeNode *root) {
return subBal(root)>=0;
}
};
class Solution {
public:
int subBal(TreeNode* root){
if(root==NULL)
return 0;
int left = subBal(root->left);
int right = subBal(root->right);
if(left<0||right<0||abs(left-right)>1) return -1;
return max(left,right)+1;
}
bool isBalanced(TreeNode *root) {
return subBal(root)>=0;
}
};
Binary Tree Inorder Traversal
這個給出兩種實現，第一種是網上的，第二種是用我說的比較通用的轉化方法做的：
[cpp] class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
vector<int> ans;
if(root==NULL) return ans;
stack<TreeNode*> s;
while(root!=NULL || !s.empty())
{
while(root!=NULL)
{
s.push(root);
root = root->left;
}
if(!s.empty())
{
root = s.top();
s.pop();
ans.push_back(root->val);
root = root->right;
}
}
return ans;
}
};
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
vector<int> ans;
if(root==NULL) return ans;
stack<TreeNode*> s;
while(root!=NULL || !s.empty())
{
while(root!=NULL)
{
s.push(root);
root = root->left;
}
if(!s.empty())
{
root = s.top();
s.pop();
ans.push_back(root->val);
root = root->right;
}
}
return ans;
}
};
[cpp] class Solution {
public:
struct Node{
TreeNode* node_;
bool sign;
Node(TreeNode* n){node_=n;sign=false;}
};
vector<int> inorderTraversal(TreeNode *root) {
stack<Node> stk;
stk.push(Node(root));
vector<int> result;
if(!root) return result;
while(!stk.empty()){
Node tmp = stk.top();
stk.top().sign = true;
if(tmp.sign){
result.push_back(tmp.node_->val);
stk.pop();
if(tmp.node_->right)
stk.push(Node(tmp.node_->right));
}else if(tmp.node_->left)
stk.push(Node(tmp.node_->left));
}
return result;
}
};
class Solution {
public:
struct Node{
TreeNode* node_;
bool sign;
Node(TreeNode* n){node_=n;sign=false;}
};
vector<int> inorderTraversal(TreeNode *root) {
stack<Node> stk;
stk.push(Node(root));
vector<int> result;
if(!root) return result;
while(!stk.empty()){
Node tmp = stk.top();
stk.top().sign = true;
if(tmp.sign){
result.push_back(tmp.node_->val);
stk.pop();
if(tmp.node_->right)
stk.push(Node(tmp.node_->right));
}else if(tmp.node_->left)
stk.push(Node(tmp.node_->left));
}
return result;
}
};
Binary Tree Level Order Traversal
[cpp] public:
vector<vector<int> > levelOrder(TreeNode *root) {
TreeNode* pre_level = root;
vector<vector<int>> result;
if(!root) return result;
queue<TreeNode*> q;
q.push(root);
result.push_back(vector<int>());
while(!q.empty()){
TreeNode* node = q.front();
q.pop();
result.back().push_back(node->val);
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
if(pre_level==node){
pre_level = q.back();
result.push_back(vector<int>());
}
}
result.pop_back();
return result;
}
};
public:
vector<vector<int> > levelOrder(TreeNode *root) {
TreeNode* pre_level = root;
vector<vector<int>> result;
if(!root) return result;
queue<TreeNode*> q;
q.push(root);
result.push_back(vector<int>());
while(!q.empty()){
TreeNode* node = q.front();
q.pop();
result.back().push_back(node->val);
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
if(pre_level==node){
pre_level = q.back();
result.push_back(vector<int>());
}
}
result.pop_back();
return result;
}
};
Binary Tree Level Order Traversal II
[cpp] class Solution {
public:
void RecBottom(TreeNode* root,vector<vector<int>>& result,int level){
if(!root) return;
result[result.size()-1-level].push_back(root->val);
RecBottom(root->left,result,level+1);
RecBottom(root->right,result,level+1);
}
int MaxHeight(TreeNode* root,int d){
if(!root) return d;
return max(MaxHeight(root->left,d+1),MaxHeight(root->right,d+1));
}
vector<vector<int> > levelOrderBottom(TreeNode *root) {
int height = MaxHeight(root,0);
vector<vector<int>> result(height);
RecBottom(root,result,0);
return result;
}
};
class Solution {
public:
void RecBottom(TreeNode* root,vector<vector<int>>& result,int level){
if(!root) return;
result[result.size()-1-level].push_back(root->val);
RecBottom(root->left,result,level+1);
RecBottom(root->right,result,level+1);
}
int MaxHeight(TreeNode* root,int d){
if(!root) return d;
return max(MaxHeight(root->left,d+1),MaxHeight(root->right,d+1));
}
vector<vector<int> > levelOrderBottom(TreeNode *root) {
int height = MaxHeight(root,0);
vector<vector<int>> result(height);
RecBottom(root,result,0);
return result;
}
};
Binary Tree Maximum Path Sum
[cpp] class Solution {
public:
int findMaxSum(TreeNode* root,int& pathMax,int& maxNode){
if(root==NULL){
pathMax = 0;
return 0;
}
if(root->val>maxNode) maxNode = root->val;
int left,right,leftPath,rightPath;
left = findMaxSum(root->left,leftPath,maxNode);
right = findMaxSum(root->right,rightPath,maxNode);
pathMax = max(max(leftPath,rightPath)+root->val,0);
return max(max(left,right),leftPath+rightPath+root->val);
}
int maxPathSum(TreeNode *root) {
if(root==NULL) return 0;
int m,maxNode=root->val;
int ans = findMaxSum(root,m,maxNode);
if(ans==0) return maxNode;
return ans;
}
};
class Solution {
public:
int findMaxSum(TreeNode* root,int& pathMax,int& maxNode){
if(root==NULL){
pathMax = 0;
return 0;
}
if(root->val>maxNode) maxNode = root->val;
int left,right,leftPath,rightPath;
left = findMaxSum(root->left,leftPath,maxNode);
right = findMaxSum(root->right,rightPath,maxNode);
pathMax = max(max(leftPath,rightPath)+root->val,0);
return max(max(left,right),leftPath+rightPath+root->val);
}
int maxPathSum(TreeNode *root) {
if(root==NULL) return 0;
int m,maxNode=root->val;
int ans = findMaxSum(root,m,maxNode);
if(ans==0) return maxNode;
return ans;
}
};
Binary Tree Zigzag Level Order Traversal
[cpp] class Solution {
public:
vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
vector<vector<int>> ans;
if(root==NULL) return ans;
queue<TreeNode*> q;
q.push(root);
TreeNode* pre = root;
vector<int> nowVec;
ans.push_back(nowVec);
while(!q.empty()){
TreeNode* tmp = q.front();
q.pop();
ans[ans.size()-1].push_back(tmp->val);
if(tmp->left!=NULL) q.push(tmp->left);
if(tmp->right!=NULL) q.push(tmp->right);
if(tmp==pre){
ans.push_back(nowVec);
if(!q.empty())
pre = q.back();
}
}
ans.pop_back();
for(int i=1;i<ans.size();i+=2)
for(int j=0,k=ans[i].size()-1;j<k;)
std::swap(ans[i][j++],ans[i][k--]);
return ans;
}
};
