二叉树是数据结构的基础，本文对LeetCode上的一些题型做一个总结
目录
一、遍历
二、根据遍历去求一些东西
一、遍历
遍历分为 递归遍历、非递归遍历、以及O(1)空间实现遍历(Morris); 以及层次遍历。
94. 二叉树的中序遍历
/*** 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>ans;vector<int> inorderTraversal(TreeNode* root) {solve(root);return ans;}void solve(TreeNode* root){if(root){solve(root->left);ans.push_back(root->val);solve(root->right);}}
};//栈 非递归
class Solution {
public:vector<int>ans;vector<int> inorderTraversal(TreeNode* root) {solve(root);return ans;}void solve(TreeNode* root){stack<TreeNode*>st;while(root || st.size()){while(root){st.push(root);root = root->left;}if(st.size()){root = st.top();st.pop();ans.push_back(root->val);root = root->right;}}}
};//以及O(1)空间实现遍历(Morris)
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int>ans;TreeNode *cur = root,*pre = nullptr;while(cur){if(cur->left){pre = cur->left;while(pre->right && pre->right != cur){pre = pre->right;}if(pre->right == nullptr){pre->right = cur;cur = cur->left;}else {pre->right = nullptr;ans.push_back(cur->val);cur = cur->right;}}else{ans.push_back(cur->val);cur = cur->right;}}return ans;}
};
145. 二叉树的后序遍历
/*** 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>ans;vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> s;TreeNode* pre = NULL;while(root || s.size()){while(root){s.push(root);root = root->left;}auto tmp = s.top();if(tmp->right == nullptr || tmp->right == pre){ans.push_back(tmp->val);pre = tmp;s.pop();}else{root = tmp->right;}}return ans;}
};
105. 从前序与中序遍历序列构造二叉树
class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {return solve(preorder.begin(),inorder.begin(),(int)preorder.size());}TreeNode* solve(vector<int>::iterator pre,vector<int>::iterator in,int len){if(len == 0)return nullptr;auto t = new TreeNode(*pre);int lenL = 0;while(*(in + lenL) != *pre)++lenL;int lenR = len - lenL - 1;t->left = solve(pre+1,in,lenL);t->right = solve(pre+lenL+1,in+lenL+1,lenR);return t;}
};
106. 从中序与后序遍历序列构造二叉树
class Solution {
public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {return solve(inorder.begin(),postorder.begin(),inorder.size());}TreeNode* solve(vector<int>::iterator in,vector<int>::iterator pos,int len){if(len == 0)return nullptr;auto t = new TreeNode(*(pos+len-1));int lenL = 0;while(*(in+lenL)!=*(pos+len-1))lenL++;int lenR = len-lenL-1;t->left = solve(in,pos,lenL);t->right = solve(in+lenL+1,pos+lenL,lenR);return t;}
};
102. 二叉树的层序遍历
class Solution {
public:vector< vector<int> > ans;vector<vector<int>> levelOrder(TreeNode* root) {solve(root);return ans;}void solve(TreeNode *root){queue<TreeNode*>q;if(root)q.push(root);while(q.size()){int n = q.size();vector<int>v;for(int i = 1;i<=n;++i){auto p = q.front();q.pop();v.push_back(p->val);if(p->left)q.push(p->left);if(p->right)q.push(p->right);}ans.push_back(v); }}
};
二、根据遍历去求一些东西
104. 二叉树的最大深度
class Solution {
public:int maxDepth(TreeNode* root) {if(!root)return 0;return 1+max(maxDepth(root->left),maxDepth(root->right));}
};113. 路径总和 II
class Solution {
public:vector< vector<int> >ans;vector<int> v;void solve(TreeNode* root,int x){if(!root)return;v.push_back(root->val);if(!root->left && !root->right && x - root->val == 0)ans.push_back(v);else {if(root->left)solve(root->left,x - root->val);if(root->right)solve(root->right,x - root->val);}v.pop_back();}vector<vector<int> > pathSum(TreeNode* root,int expectNumber) {solve(root,expectNumber);return ans;}};
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 isSymmetric(TreeNode* root) {return solve(root,root);}bool solve(TreeNode *p,TreeNode *q){if(!p && !q)return true;if(!p|| !q)return false;if(p->val != q->val)return false;return solve(p->left,q->right) && solve(p->right,q->left);}
};
108. 将有序数组转换为二叉搜索树
class Solution {
public:TreeNode* sortedArrayToBST(vector<int>& nums) {if(nums.size() == 0)return nullptr;return solve(nums,0,nums.size()-1);}TreeNode* solve(vector<int>& a,int l,int r){if(l>r)return nullptr;int m = l+r>>1;auto root = new TreeNode(a[m]);root -> left = solve(a,l,m-1);root -> right = solve(a,m+1,r);return root;}
};
116. 填充每个节点的下一个右侧节点指针
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) {solve(root);return root;}void solve(Node *root){if(!root || !root->left) return ;root->left->next = root->right;if(root->next) root->right->next = root->next->left;solve(root->left);solve(root->right);}
};
111. 二叉树的最小深度
class Solution {
public:int minDepth(TreeNode* root) {if(!root)return 0;int l = minDepth(root->left),r = minDepth(root->right);return l&&r? 1+min(l,r):1+l+r;}
};
124. 二叉树中的最大路径和
class Solution {
public:int ans = INT_MIN;int maxPathSum(TreeNode* root) {solve(root);return ans;}int solve(TreeNode* root){if(!root)return 0;int l = max(0,solve(root->left));int r = max(0,solve(root->right));ans = max(ans,l+r+root->val);return max(l,r) + root->val;}
};
236. 二叉树的最近公共祖先
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(!root)return nullptr;if(root == p || root == q)return root;TreeNode *left = lowestCommonAncestor(root->left,p,q);TreeNode *right = lowestCommonAncestor(root->right,p,q);if(left && right)return root;if(left)return left;if(right)return right;return nullptr;}
};