leetcode-二叉树专题

1. 判断相同

100. 相同的树

class Solution {
public:bool isSameTree(TreeNode* p, TreeNode* q) {if(!p&&!q) return true;if(!p||!q) return false;if(p->val!=q->val) return false;return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);}
};

101. 对称二叉树

class Solution {
public:bool isSame(TreeNode* p,TreeNode* q){if(!p&&!q) return true;if(!p||!q) return false;if(p->val!=q->val) return false;return isSame(p->left,q->right)&&isSame(p->right,q->left);}bool isSymmetric(TreeNode* root) {return isSame(root,root);}
};

2. 翻转

226. 翻转二叉树

class Solution {
public:TreeNode* invertTree(TreeNode* root) {if(!root) return NULL;TreeNode* left=invertTree(root->left);TreeNode* right=invertTree(root->right);root->left=right;root->right=left;return root;}
};

3. 深度

111. 二叉树的最小深度

class Solution {
public:int minDepth(TreeNode* root) {if(!root) return 0;int left_minDepth=minDepth(root->left);int right_minDepth=minDepth(root->right);if(!left_minDepth&&!right_minDepth) return 1;else if(!left_minDepth&&right_minDepth) return right_minDepth+1;else if(left_minDepth&&!right_minDepth) return left_minDepth+1;return min(left_minDepth,right_minDepth)+1;}
};

104. 二叉树的最大深度

class Solution {
public:int maxDepth(TreeNode* root) {if(!root) return 0;return max(maxDepth(root->left),maxDepth(root->right))+1;}
};

543. 二叉树的直径

class Solution {
public:int res=0;int maxHeight(TreeNode* root){ //返回树的高度if(!root) return 0;int left_height=maxHeight(root->left);int right_height=maxHeight(root->right);res=max(res,left_height+right_height);return max(left_height,right_height)+1;}int diameterOfBinaryTree(TreeNode* root) {maxHeight(root);return res;}
};

4. 遍历

144. 二叉树的前序遍历

class Solution {
public:void travel(TreeNode* root,vector<int>& res){if(!root) return;res.push_back(root->val);travel(root->left,res);travel(root->right,res);}vector<int> preorderTraversal(TreeNode* root) {vector<int> res;travel(root,res);return res;}
};

class Solution {
public:vector<int> travel(TreeNode* root){vector<int> res;stack<TreeNode*> stk;while(root||!stk.empty()){while(root){res.push_back(root->val);stk.push(root);root=root->left;}root=stk.top();stk.pop();root=root->right;}return res;}vector<int> preorderTraversal(TreeNode* root) {return travel(root);}
};

145. 二叉树的后序遍历

class Solution {
public:vector<int> res;void travel(TreeNode* root){if(!root) return;travel(root->left);travel(root->right);res.push_back(root->val);}vector<int> postorderTraversal(TreeNode* root) {travel(root);return res;}
};

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> res;stack<TreeNode*> stk;TreeNode* prev;while(root||!stk.empty()){while(root){ //先把最左的节点一路入栈stk.push(root);root=root->left;}root=stk.top();stk.pop();if(!root->right||prev==root->right){prev=root;res.push_back(root->val);root=NULL;}else{stk.push(root);root=root->right;}}return res;}
};

94. 二叉树的中序遍历

class Solution {
public:void travel(TreeNode* root,vector<int>& res){if(!root) return;travel(root->left,res);res.push_back(root->val);travel(root->right,res);}vector<int> inorderTraversal(TreeNode* root) {vector<int> res;travel(root,res);return res;}
};

class Solution {
public:vector<int> travel(TreeNode* root){vector<int> res;stack<TreeNode*> stk;while(root||!stk.empty()){while(root!=NULL){stk.push(root);root=root->left;}root=stk.top();stk.pop();res.push_back(root->val);root=root->right;}return res;}vector<int> inorderTraversal(TreeNode* root) {return travel(root);}
};

102. 二叉树的层序遍历

class Solution {
public:vector<vector<int>> res;void search(TreeNode* root){queue<TreeNode*> q;queue<int> idx;q.push(root);idx.push(1);while(!q.empty()){TreeNode* p=q.front();q.pop();int i=idx.front();idx.pop();if(res.size()<i) res.push_back({});res[i-1].push_back(p->val);cout<<i<<":"<<p->val<<endl;if(p->left){q.push(p->left);idx.push(i+1);}if(p->right){q.push(p->right);idx.push(i+1);} }}vector<vector<int>> levelOrder(TreeNode* root) {if(!root) return res;search(root);return res;}
};

199. 二叉树的右视图

class Solution {
public:vector<vector<int>> res;void search(TreeNode* root){queue<TreeNode*> q;queue<int> idx;q.push(root);idx.push(1);while(!q.empty()){TreeNode* p=q.front();q.pop();int i=idx.front();idx.pop();if(res.size()<i) res.push_back({});res[i-1].push_back(p->val);cout<<i<<":"<<p->val<<endl;if(p->left){q.push(p->left);idx.push(i+1);}if(p->right){q.push(p->right);idx.push(i+1);} }}vector<int> rightSideView(TreeNode* root) {vector<int> final_res;if(!root) return final_res;search(root);for(int i=0;i<res.size();i++){final_res.push_back(res[i][res[i].size()-1]);}return final_res;}
};

5. 恢复二叉树

105. 从前序与中序遍历序列构造二叉树

class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {if(preorder.size()==0) return NULL;int idx=-1;for(int i=0;i<inorder.size();i++){if(inorder[i]==preorder[0]){idx=i; //找到左右子树的分叉点(即根节点)break;}}TreeNode* p=new TreeNode(inorder[idx]);cout<<inorder[idx];vector<int> pre_left(preorder.begin()+1,preorder.begin()+idx+1); //preleft=preorder[1,idx] 要排除掉第0个(即根节点)vector<int> pre_right(preorder.begin()+idx+1,preorder.end());vector<int> in_left(inorder.begin(),inorder.begin()+idx); //不用排除掉第0个, 但要排除掉idxvector<int> in_right(inorder.begin()+idx+1,inorder.end());p->left=buildTree(pre_left,in_left);p->right=buildTree(pre_right,in_right);return p;}
};

889. 根据前序和后序遍历构造二叉树

class Solution {
public:TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {if(preorder.size()==0) return NULL;if(preorder.size()==1){TreeNode* p=new TreeNode(preorder[0]);return p;}int idx=-1; //后序遍历序列中, idx及其左边为左子树, 右边为右子树for(int i=0;i<postorder.size();i++){if(postorder[i]==preorder[1]){ idx=i;break;}}TreeNode* p=new TreeNode(preorder[0]);vector<int> left_pre(preorder.begin()+1,preorder.begin()+idx+2);vector<int> right_pre(preorder.begin()+idx+2,preorder.end());vector<int> left_post(postorder.begin(),postorder.begin()+idx+1);vector<int> right_post(postorder.begin()+idx+1,postorder.end()-1);p->left=constructFromPrePost(left_pre,left_post);p->right=constructFromPrePost(right_pre,right_post);return p;}
};

108. 将有序数组转换为二叉搜索树

class Solution {
public:TreeNode* sortedArrayToBST(vector<int>& nums) {if(nums.size()==0) return NULL;int l=0,r=nums.size()-1,mid=(l+r)/2;TreeNode* p=new TreeNode(nums[mid]);vector<int> left_nums(nums.begin(),nums.begin()+mid);vector<int> right_nums(nums.begin()+mid+1,nums.end());p->left=sortedArrayToBST(left_nums);p->right=sortedArrayToBST(right_nums);return p;}
};

6. 路径总和

112. 路径总和

class Solution {
public:vector<int> res;bool helper(TreeNode* root,int sum,int targetSum){if(!root) return false;if(!root->left&&!root->right){sum+=root->val;return sum==targetSum;}sum+=root->val;return helper(root->left,sum,targetSum)||helper(root->right,sum,targetSum);}bool hasPathSum(TreeNode* root, int targetSum) {return helper(root,0,targetSum);}
};

113. 路径总和 II

class Solution {
public:vector<int> path;vector<vector<int>> res;void helper(TreeNode* root, int sum,int targetSum){if(!root) return;if(!root->left&&!root->right){sum+=root->val;path.push_back(root->val);if(sum==targetSum) res.push_back(path);path.pop_back();}else{sum+=root->val;path.push_back(root->val);helper(root->left,sum,targetSum);helper(root->right,sum,targetSum);path.pop_back();}}vector<vector<int>> pathSum(TreeNode* root, int targetSum) {helper(root,0,targetSum);return res;}
};

437. 路径总和 III

class Solution {
public:unordered_map<long long,int> prefix; //存储根节点到每一个节点的路径长度, 后用前缀和就可以求出所有节点之间的路经长度int helper(TreeNode* root,long long sum,int targetSum){if(!root) return 0;int cnt=0; //满足条件的路径总数sum+=root->val;if(prefix.find(sum-targetSum)!=prefix.end()){cnt=prefix[sum-targetSum];}prefix[sum]++;cnt+=helper(root->left,sum,targetSum);cnt+=helper(root->right,sum,targetSum);prefix[sum]--;return cnt;}  int pathSum(TreeNode* root, int targetSum) {prefix[0]=1;return helper(root,0,targetSum);}
};

7.else

114. 二叉树展开为链表

class Solution {
public:void flatten(TreeNode* root) {if(!root) return;TreeNode* prev=NULL;TreeNode* head=root;while(head){if(head->left){ //左子树存在的话, 找到左子树中的最右节点prev=head->left;while(prev->right) prev=prev->right;prev->right=head->right;head->right=head->left;head->left=NULL;}head=head->right;}}
};

236. 二叉树的最近公共祖先

class Solution {
public:vector<TreeNode*> path2p;vector<TreeNode*> path2q;bool findPath(TreeNode* root,TreeNode* p,vector<TreeNode*>& path){if(!root) return false;path.push_back(root);if(root==p){return true;}bool isFind=false;if(!isFind){isFind=findPath(root->left,p,path);}if(!isFind){isFind=findPath(root->right,p,path);}if(!isFind) path.pop_back();return isFind;}   TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {findPath(root,p,path2p);findPath(root,q,path2q);for(int i=path2p.size()-1;i>=0;i--){for(int j=path2q.size()-1;j>=0;j--){if(path2p[i]->val==path2q[j]->val) return path2p[i];}}return NULL;}
};