二叉树结构：
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) {}
};
一.基本问题
遍历
前序遍历
leetcode 144 二叉树的前序遍历
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
if(!root) return ans;
stack<TreeNode*> st;
st.push(root);
while(!st.empty()){
TreeNode *cur=st.top();
st.pop();
ans.push_back(cur->val);
if(cur->right)
st.push(cur->right);
if(cur->left)
st.push(cur->left);
}
return ans;
}
};
leetcode 255 验证前序遍历序列二叉搜索树
给定序列，判定有没有可能是二叉搜索树的前序遍历
利用preorder的特性：
遍历preorder
1）如果当前值cur小于栈顶值，说明该值是栈顶元素左子树的值，将其压入栈中;
2）如果当前值cur大于栈顶值，说明某节点的左子树已经遍历结束，cur是某元素右子树的值，要弹出栈；
并用栈顶的值更新lower_bound，且后面遍历的所有数都必须大于这个lower_bound；
这个比较、弹出、更新lower_bound的过程一直进行直到当前遍历的值cur小于栈顶。
class Solution {
public:
bool verifyPreorder(vector<int>& preorder) {
int lower_bound=INT_MIN;
stack<int> st;
for(auto cur:preorder){
if(cur<lower_bound) return false;
while(!st.empty()&&cur>st.top()){
lower_bound=st.top();
st.pop();
}
st.push(cur);
}
return true;
}
}
后序遍历
遍历顺序是：左右中；可以先求中右左的顺序，再逆序过来
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
if(!root) return ans;
stack<TreeNode*> st1;
stack<TreeNode*> st2;
st1.push(root);
while(!st1.empty()){
TreeNode* cur=st1.top();
st1.pop();
st2.push(cur);
if(cur->left)
st1.push(cur->left);
if(cur->right)
st1.push(cur->right);
}
while(!st2.empty()){
ans.push_back(st2.top()->val);
st2.pop();
}
return ans;
}
};
中序遍历
leetcode 95二叉树的中序遍历
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
if(!root) return ans;
stack<TreeNode*> st;
while(!st.empty()||cur){
while(cur){
st.push(cur);
cur=cur->left;
}
TreeNode* cur=st.top();
st.pop();
ans.push_back(cur->val);
cur=cur->right;
}
return ans;
}
leetcode 98:利用中序遍历来验证是否二叉搜索树
bool isBST(TreeNode* root,long long& prev){
if(root){
if(!isBST(root->left,prev)) return false;
if(prev>=root->val) return false;//中序遍历打印时机
prev=root->val;
return isBST(root->right,prev);
}
return true;
}
bool isValidBST(TreeNode* root) {
long long prev=LONG_MIN;
return isBST(root,prev);
}
leetcode 99:利用中序遍历来恢复二叉搜索树
class Solution {
public:
TreeNode* pre=nullptr;
TreeNode* x=nullptr;
TreeNode* y=nullptr;
void dfs(TreeNode* root){
if(root){
dfs(root->left);
if(pre==nullptr) pre=root;
if(root->val<pre->val){//用x，y表示要交换的两个节点
y=root;
if(x==nullptr)
x=pre;
}
pre=root;
dfs(root->right);
}
}
void recoverTree(TreeNode* root) {
dfs(root);
if(x!=nullptr&&y!=nullptr){
int temp=x->val;
x->val=y->val;
y->val=temp;
}
}
};
leetcode 230 求二叉搜索树的第k小元素
先求出中序序列，返回第k个即可
进阶：
https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/solution/er-cha-sou-suo-shu-zhong-di-kxiao-de-yuan-su-jin-j/
```
class Solution {
private:
unordered_map[HTML_REMOVED] leftchilds;
unordered_map[HTML_REMOVED] rightchilds;
public:
int myKthSmallest(TreeNode root,int k){
TreeNode cur = root;
int rank = leftchilds[cur] + 1;
while(k != rank){
if(k < rank){
cur = cur -> left;
rank -= rightchilds[cur] + 1;
}else{
cur = cur -> right;
rank += leftchilds[cur] + 1;
}
}
return cur -> val;
}
int memoTree(TreeNode* root){
if(!root){
return 0;
}
leftchilds[root] = memoTree(root -> left);
rightchilds[root] = memoTree(root -> right);
return leftchilds[root] + rightchilds[root] + 1;
}
int kthSmallest(TreeNode* root, int k) {
if(!root){
return 0;
}
memoTree(root);
return myKthSmallest(root,k);
}
};
```
莫里斯遍历：空间复杂度O(1)
来到的当前节点，记为cur；
1）如果cur无左孩子，cur向右移动（cur=cur->right）
2）如果cur有左孩子，找到cur左子树上的最右节点，记为most_right
如果most_right的right指针指向空，让它指向cur，cur向左移动
如果most_right的right指针指向cur，让它指向空，cur向右移动
基本模板：
void morrisTraversal(TreeNode* root) {
if (root == nullptr) return;
TreeNode* cur = root;
while (cur) {
if (cur->left == nullptr) {
//打印时机
cur = cur->right;
}
else {
TreeNode* most_right = cur->left;
while (most_right->right != nullptr && most_right->right != cur)
most_right = most_right->right;
if (most_right->right == nullptr) {
most_right->right = cur;
cur = cur->left;
}
else {
most_right->right = nullptr;
//打印时机
cur = cur->right;
}
}
}
}
leetcode 98 利用莫里斯遍历恢复二叉搜索树
class Solution {
public:
TreeNode* pre=nullptr;
TreeNode* x=nullptr;
TreeNode* y=nullptr;
void morrisTraversal(TreeNode* root) {
if (root == nullptr) return;
TreeNode* cur = root;
while (cur) {
if (cur->left == nullptr) {
}
else {
TreeNode* most_right = cur->left;
while (most_right->right != nullptr && most_right->right != cur)
most_right = most_right->right;
if (most_right->right == nullptr) {
most_right->right = cur;
cur = cur->left;
continue;
}
else {
most_right->right = nullptr;
}
}
if(pre==nullptr) pre=cur;
if(pre->val>cur->val){
y=cur;
if(x==nullptr){
x=pre;
}
}
pre=cur;
cur=cur->right;
}
}
void recoverTree(TreeNode* root) {
morrisTraversal(root);
if(x!=nullptr&&y!=nullptr){
int temp=x->val;
x->val=y->val;
y->val=temp;
}
}
};
层次遍历
leetcode 102 二叉树层次遍历
leetcode 107 二叉树的层次遍历2：从下往上的遍历
leetcode 103 二叉树的锯齿形层次遍历
leetcode 104 求二叉树的最大深度：使用层次遍历
leetcode 116:填充每个节点的下一个右侧指针（完美二叉树）
leetcode 117:填充每个节点的下一个右侧指针（普通二叉树）
leetcode 199:二叉树的右视图
leetcode 102 二叉树层次遍历
如果不需要确定当前遍历到了哪一层
while queue 不空：
cur = queue.pop()
将 cur的值 塞到 ans 中；
if cur的左儿子 有效：
queue.push(左儿子)
if cur的右儿子 有效：
queue.push(右儿子)
如果要确定当前遍历到了哪一层
while queue 不空：
size = queue.size()
声明临时vector
while (size --) {
cur = queue.pop()
将 cur的值 加入 临时vector
if cur的左儿子 有效：
queue.push(左儿子)
if cur的右儿子 有效：
queue.push(右儿子)
}
将 临时vector 塞进 ans 中
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if(!root) return res;
queue<TreeNode*> que;
que.push(root);
while (que.size() != 0) {
int size = que.size();
vector<int> temp;
while (size --) {
TreeNode* cur = que.front();
que.pop();
temp.push_back(cur->val);
if(cur->left)
que.push(cur->left);
if(cur->right)
que.push(cur->right);
}
res.push_back(temp);
}
return res;
}
};
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
dfs(res, root, 0);
return res;
}
void dfs(vector<vector<int>>& res, TreeNode* root, int level) {
if (!root) return;
if (level >= res.size())
res.push_back(vector<int>());
res[level].push_back(root->val);
dfs(res, root->left, level + 1);
dfs(res, root->right, level + 1);
}
};
leetcode 107 二叉树的层次遍历2：从下往上的遍历
相比上题，简单的把上题的结果逆序即可
leetcode 103 二叉树的锯齿形层次遍历
在原来的模板基础上，维护level作为层数；
在插入元素到临时vector时，根据level的奇偶来进行正序或逆序的插入即可
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> res;
if (root == NULL) return {};
queue<TreeNode*> q;
q.push(root);
int level=0;
while (!q.empty())
{
vector<int>temp; //存放每一层的元素值
int count=q.size(); //队列大小表示当前层数的元素个数
while(count--) //count--逐个对该层元素进行处理
{
TreeNode *t=q.front();
q.pop();
if(level%2 ==0)
temp.push_back(t->val);
else
temp.insert(temp.begin(),t->val);
if(t->left) q.push(t->left);
if(t->right)q.push(t->right);
}
level++;
res.push_back(temp); //将当层元素的vector加入res中
}
return res;
}
};
leetcode 104 求二叉树的最大深度：使用层次遍历
class Solution {
public:
int maxDepth(TreeNode* root) {
if(!root) return 0;
queue<TreeNode*> q;
q.push(root);
int level=0;
while(!q.empty()){
int count=q.size();
while(count--){
TreeNode* cur=q.front();
q.pop();
if(cur->left)
q.push(cur->left);
if(cur->right)
q.push(cur->right);
}
level++;
}
return level;
}
};
leetcode 116:填充每个节点的下一个右侧指针（完美二叉树）
class Solution {
public:
Node* connect(Node* root) {
if(root == nullptr) return root;
queue<Node*> q({root});
while(!empty(q)){
Node* tmp = new Node(-1);
int count = q.size();
while(count--){
tmp->next = q.front();
q.pop();
tmp = tmp->next;
if(tmp->left)
q.push(tmp->left);
if(tmp->right)
q.push(tmp->right);
}
}
return root;
}
};
class Solution {
public:
void connect_m(Node* root, Node* nextOne) {
if(root == nullptr) return;
connect_m(root->left, root->right);
root->next = nextOne;
connect_m(root->right, (nextOne ? nextOne->left: nullptr));
}
Node* connect(Node* root) {
connect_m(root, nullptr);
return root;
}
};
leetcode 117:填充每个节点的下一个右侧指针（普通二叉树）
思路：类似层次遍历的思想
当前层cur通过next不断右移；每次处理下一层级的节点相连；
处理完一层后移动到下一层；直到没有下一层为止；
Node connect(Node root) {
Node cur = root;
while (cur != null) {
Node dummy = new Node();
Node tail = dummy;
//遍历 cur 的当前层
while (cur != null) {
if (cur.left != null) {
tail.next = cur.left;
tail = tail.next;
}
if (cur.right != null) {
tail.next = cur.right;
tail = tail.next;
}
cur = cur.next;
}
//更新 cur 到下一层
cur = dummy.next;
}
return root;
}
leetcode 199:二叉树的右视图
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> ans;
if(!root) return ans;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
int count=q.size();
while(count--){
TreeNode* cur=q.front();
q.pop();
if(count==0)
ans.push_back(cur->val);
if(cur->left)
q.push(cur->left);
if(cur->right)
q.push(cur->right);
}
}
return ans;
}
};
由序列构造二叉树
leetcode 105 根据一棵树的前序遍历与中序遍历构造二叉树。
拿到中序序列的值和对应的下标；
这里可以维护一个全局的pre序列的index，
在递归先建立左子树再建立右子树时，可以保证每次递归建立的root的值是前序序列的顺序
class Solution {
unordered_map<int, int> mp;
int idx = 0;
int n;
public:
TreeNode* buildTree(vector<int>& pre, vector<int>& in) {
n = in.size();
for (int i = 0; i < n; ++i) mp[in[i]] = i;
return build(pre, 0, n - 1);
}
TreeNode* build(vector<int>& pre, int l, int r) {
if (l > r) return nullptr;
int i = mp[pre[idx]];
TreeNode* new_node = new TreeNode(pre[idx++]);
new_node->left = build(pre, l, i - 1);
new_node->right = build(pre, i + 1, r);
return new_node;
}
};
leetcode 106 根据一棵树的中序遍历与后序遍历构造二叉树
拿到中序序列的值和对应的下标；
这里可以维护一个全局的pre序列的index，
在递归先建立右子树再建立左子树时，可以保证每次递归建立的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:
unordered_map<int,int> mp;
int idx;
int n;
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
n=inorder.size();
idx=n-1;
for(int i=0;i<n;i++)
mp[inorder[i]]=i;
return build(postorder,0,n-1);
}
TreeNode* build(vector<int>& postorder,int l,int r){
if(l>r) return nullptr;
int i=mp[postorder[idx]];
TreeNode* new_node=new TreeNode(postorder[idx--]);
new_node->right=build(postorder,i+1,r);
new_node->left=build(postorder,l,i-1);
return new_node;
}
};
leetcode 255[变形题]根据前序遍历序列和二叉搜索树构造树
将前序遍历序列进行排序成中序遍历，这样就可以转化为leetcode 105了；
leetcode 108 将有序数组转换为二叉树
/**
* 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) {
int n=nums.size();
return build(nums,0,n-1);
}
TreeNode* build(vector<int>& nums,int l,int r){
if(l>r) return nullptr;
int i=(l+r)/2;
TreeNode* new_node=new TreeNode(nums[i]);
new_node->left=build(nums,l,i-1);
new_node->right=build(nums,i+1,r);
return new_node;
}
};
leetcode 109 有序链表转换为二叉搜索树
和上题的有序数组相比，
通过快慢指针找到中间节点
注意边界条件的处理
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
/**
* 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* sortedListToBST(ListNode* head) {
if(!head) return nullptr;
ListNode* fast=head;
ListNode* slow=fast;
ListNode* dummy=new ListNode(-1,slow);
ListNode* pre=dummy;
while(fast->next!=nullptr&&fast->next->next!=nullptr){
pre=slow;
slow=slow->next;
fast=fast->next->next;
}
pre->next=nullptr;
TreeNode* new_node=new TreeNode(slow->val);
if(pre==dummy) new_node->left=nullptr;
else new_node->left=sortedListToBST(head);
new_node->right=sortedListToBST(slow->next);
return new_node;
}
};
递归解决二叉树问题：
1.确定递归函数的参数和返回值
2.确定终止条件
3.确定单层递归的逻辑
1)是否满足某种性质类：
leetcode 98 是否为二叉搜索树
leetcode 100 两棵二叉树是否相同
leetcode 101 二叉树是否是镜像对称的
leetcode 110 二叉树是否高度平衡
2)定义递归函数，递归的每层的逻辑一致：求深度，路径和等
leetcode 104 求二叉树的最大深度
leetcode 111 求二叉树的最小深度
leetcode 124 求二叉树的最大路径和
leetcode 156 上下翻转二叉树
leetcode 222 完全二叉树的节点个数
leetcode 235 二叉搜索树的最近公共祖先
leetcode 236 二叉树的公共祖先
leetcode 250 计数相同值子树的个数
3)树上进行dfs，到达终点时结算
leetcode 112 求二叉树的路径总和
leetcode 113 求二叉树的路径总和2
leetcode 437 求路径总和等于给定值的路径数
leetcode 129 求根到叶子节点数字之和
leetcode 257 二叉树的所有路径（根到叶子节点）
leetcode 98 是否为二叉搜索树
int isBSTUtil(struct TreeNode* node, long long min, long long max)
{
/* 是一颗空树 */
if (node==NULL)
return 1;
/* 结点的值小于等于最小值，或者大于等于最大值都是不合理的，返回false */
if (node->val <= min || node->val >= max)
return 0;
/*否则递归地判断结点的左子树和右子树*/
return
isBSTUtil(node->left, min, node->val) &&
isBSTUtil(node->right, node->val, max);
}
bool isValidBST(struct TreeNode* root){
return isBSTUtil(root,LONG_MIN, LONG_MAX);
}
leetcode 100 两棵二叉树是否相同
/**
* 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:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p!=nullptr&&q!=nullptr){
return p->val==q->val&&isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}
else{
if(p==nullptr&&q==nullptr) return true;
else return false;
}
}
};
leetcode 101 是否对称二叉树
class Solution {
public:
bool compare(TreeNode* left, TreeNode* right) {
if (left == NULL && right != NULL) return false;
else if (left != NULL && right == NULL) return false;
else if (left == NULL && right == NULL) return true;
else if (left->val != right->val) return false;
else return compare(left->left, right->right) && compare(left->right, right->left);
}
bool isSymmetric(TreeNode* root) {
if (root == NULL) return true;
return compare(root->left, root->right);
}
};
leetcode 110 二叉树是否高度平衡
/**
* 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;
int leftmax=maxdepth(root->left);
int rightmax=maxdepth(root->right);
if(leftmax==-1||rightmax==-1||leftmax>rightmax+1||leftmax+1<rightmax)
return -1;
return leftmax>rightmax?leftmax+1:rightmax+1;
}
bool isBalanced(TreeNode* root) {
return maxdepth(root)==-1?false:true;
}
};
leetcode 104 求二叉树的最大深度
/**
* 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;
return max(maxDepth(root->left),maxDepth(root->right))+1;
}
};
leetcode 111 二叉树的最小深度
/**
* 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 minDepth(TreeNode* root) {
if(root == nullptr) return 0;
if(root->left == nullptr) return minDepth(root->right) + 1;
if(root->right == nullptr) return minDepth(root->left) + 1;
return min(minDepth(root->left), minDepth(root->right)) + 1;
}
};
leetcode 222 完全二叉树的节点个数
要用到完全二叉树的性质来减少递归次数
class Solution {
public:
// 统计树的深度
int countLevels(TreeNode* root) {
int levels = 0;
while (root) {
root = root->left;
levels += 1;
}
return levels;
}
int countNodes(TreeNode* root){
// 2. 利用完全二叉树性质简化遍历次数
if(root == nullptr) return 0;
int left_levels = countLevels(root->left);
int right_levels = countLevels(root->right);
// 左子树深度等于右子树深度, 则左子树是满二叉树
if(left_levels == right_levels){
return countNodes(root->right) + (1<<left_levels);
}else{
return countNodes(root->left) + (1<<right_levels);
}
}
};
leetcode 156 翻转二叉树
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(!root) return nullptr;
TreeNode* l=invertTree(root->left);
TreeNode* r=invertTree(root->right);
root->left=r;
root->right=l;
return root;
}
};
leetcode 235 二叉搜索树的最近公共祖先
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr) return nullptr;
if (p->val < root->val && q->val < root->val) return lowestCommonAncestor(root->left, p, q);
if (p->val > root->val && q->val > root->val) return lowestCommonAncestor(root->right, p, q);
return root;
}
};
leetcode 236 二叉树的最近公共祖先
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr || root == p || root == q) return root;
TreeNode* l = lowestCommonAncestor(root->left, p, q);
TreeNode* r = lowestCommonAncestor(root->right, p, q);
if (l && r) return root;
return l ? l : r;
}
};
leetcode 250 计数相同值子树的个数
递归函数1定义：对二叉树进行dfs遍历
递归函数2定义：给定root，返回以这个root为根的子树是否为给定值
class Solution {
public:
int res = 0;
int countUnivalSubtrees(TreeNode* root) {
if (!root) return res;
if (isUnival(root, root->val)) ++res;
countUnivalSubtrees(root->left);
countUnivalSubtrees(root->right);
return res;
}
bool isUnival(TreeNode *root, int val) {
if (!root) return true;
return root->val == val && isUnival(root->left, val) && isUnival(root->right, val);
}
};
在后序遍历的过程中，对于当前遍历到的节点，如果对其左右子节点分别递归调用函数，返回均为 true 的话，那么说明当前节点的值和左右子树的值都相同，那么又多了一棵树，所以结果自增1，然后返回当前节点值和给定值(其父节点值)是否相同，从而回归上一层递归调用
class Solution {
public:
int countUnivalSubtrees(TreeNode* root) {
int res = 0;
isUnival(root, -1, res);
return res;
}
bool isUnival(TreeNode* root, int val, int& res) {
if (!root) return true;
if (!isUnival(root->left, root->val, res) | !isUnival(root->right, root->val, res)) {
return false;
}
//不能使用双竖杠或的原因是，如果是双竖杠或，一旦左半边为 true 了，整个就直接是 true //了，右半边就不会再计算了，这样的话，一旦右子树中有值相同的子树也不会被计算到结果 res 中了
++res;
return root->val == val;
}
};
leetcode 112 求二叉树是否存在路径（从根节点出发到叶子节点），路径值的总和为给定值
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
if(!root)
return false;
if(root->val == sum && !root->left && !root->right)
return true;
return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
}
};
leetcode 113 求上题的具体路径
class Solution {
public:
vector<vector<int>> ans;
vector<int> path;
vector<vector<int>> pathSum(TreeNode* root, int sum) {
if(!root) return ans;
dfs(root,sum,path);
return ans;
}
void dfs(TreeNode* root, int sum,vector<int> path){
if(root->left==nullptr&&root->right==nullptr){
if(sum!=root->val) return;
path.push_back(root->val);
ans.push_back(path);
return;
}
path.push_back(root->val);
if(root->left)
dfs(root->left,sum-root->val,path);
if(root->right)
dfs(root->right,sum-root->val,path);
}
};
leetcode 437 求路径总和等于给定值的路径数（与上题不同，路径不用从根出发和从叶子结束）
在上题思路的基础上：
1）不用从根出发：先对二叉树进行遍历，再在每个节点开始dfs
2）不用从叶子结束：不用等到当前节点是叶子才进行判断
class Solution {
public:
int ans = 0;
void dfs(TreeNode* root, int sum)
{
if(root == nullptr)
return;
sum -= root->val;
if(sum == 0)
ans++;
dfs(root->left, sum);
dfs(root->right, sum);
}
int pathSum(TreeNode* root, int sum) {
if(root == nullptr)
return ans;
dfs(root, sum);
pathSum(root->left, sum);
pathSum(root->right, sum);
return ans;
}
};
leetcode 129 求根到叶子节点数字之和
给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
例如，从根到叶子节点路径 1->2->3 代表数字 123。
计算从根到叶子节点生成的所有数字之和。
/**
* 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 ans=0;
int sumNumbers(TreeNode* root) {
if(!root) return 0;
dfs(root,0);
return ans;
}
void dfs(TreeNode* root,int cur){
cur=cur*10+root->val;
if(root->left==nullptr&&root->right==nullptr){
ans+=cur;
return;
}
if(root->left)
dfs(root->left,cur);
if(root->right)
dfs(root->right,cur);
}
};
leetcode 257 二叉树的所有路径（根到叶子节点）
/**
* 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<string> ans;
vector<string> binaryTreePaths(TreeNode* root) {
if(!root) return ans;
dfs(root,"");
return ans;
}
void dfs(TreeNode* root,string temp){
if(root->left==nullptr&&root->right==nullptr){
temp+=to_string(root->val);
ans.push_back(temp);
return;
}
temp+=to_string(root->val)+"->";
if(root->left)
dfs(root->left,temp);
if(root->right)
dfs(root->right,temp);
}
};
leetcode 124 二叉树中的最大路径和
这里的路径定义：从任意节点到任意节点
递归函数定义：返回当前节点的单边最大路径和
class Solution {
public:
int ans=INT_MIN;
int maxPathSum(TreeNode* root) {
if(!root) return 0;
single_side_max(root);
return ans;
}
int single_side_max(TreeNode* root){
if(!root) return 0;
int left_max=max(0,single_side_max(root->left));
int right_max=max(0,single_side_max(root->right));
ans=max(ans,left_max+right_max+root->val);
return max(left_max,right_max)+root->val;
}
};
leetcode 156 上下翻转二叉树
给定一个二叉树，其中所有的右节点要么是具有兄弟节点（拥有相同父节点的左节点）的叶节点，要么为空
将此二叉树上下翻转并将它变成一棵树， 原来的右节点将转换成左叶节点。返回新的根。
class Solution {
public:
TreeNode* upsideDownBinaryTree(TreeNode* root) {
if(!root || !root->left) return root;
TreeNode* l = root->left;//左右子节点存取来
TreeNode* r = root->right;
root->left = NULL;//上下断开
root->right = NULL;
TreeNode* p = upsideDownBinaryTree(l);//根节点
l->left = r;//跟上面连接起来
l->right = root;
return p;
}
};
将二叉树转换为其他结构
leetcode 114 二叉树展开为链表
class Solution {
public:
void flatten(TreeNode* root) {
while (root != nullptr) {
if (root->left != nullptr) {
auto most_right = root->left; // 如果左子树不为空, 那么就先找到左子树的最右节点
while (most_right->right != nullptr) most_right = most_right->right; // 找最右节点
most_right->right = root->right; // 然后将跟的右孩子放到最右节点的右子树上
root->right = root->left; // 这时候跟的右孩子可以释放, 因此我令左孩子放到右孩子上
root->left = nullptr; // 将左孩子置为空
}
root = root->right; // 继续下一个节点
}
return;
}
};
class Solution {
public:
vector<TreeNode*> generateTrees(int st,int n) {
// 边界条件
vector<TreeNode*> ans;
if(st > n) return {NULL}; // 一定要返回{NULL}集合，否则上级树根节点i取边界得时候就不能去全排列了，有一个for循环会直接跳过
// 递归代码
for(int i=st;i<=n;i++){
for(auto& l : generateTrees(st,i-1)){
for(auto& r : generateTrees(i+1,n)){
TreeNode* root = new TreeNode(i,l,r);
ans.push_back(root);
}
}
}
return ans;
}
vector<TreeNode*> generateTrees(int n) {
if(n == 0) return {};
return generateTrees(1,n);
}
};
class Solution {
vector<vector<vector<TreeNode*>> > memo; //1 加上记忆化后果然好多了，可见真的重复计算了好多
public:
vector<TreeNode*> generateTrees(int st,int ed) {
// 边界条件
vector<TreeNode*> ans;
if(st > ed) return {NULL};
if(!memo[st][ed].empty()) return memo[st][ed]; //4 记忆化代码
// 递归代码
for(int i=st;i<=ed;i++){
for(auto& l : generateTrees(st,i-1)){
for(auto& r : generateTrees(i+1,ed)){
TreeNode* root = new TreeNode(i,l,r);
ans.push_back(root);
}
}
}
return memo[st][ed]=ans; //3 记忆化添加得代码
}
vector<TreeNode*> generateTrees(int n) {
memo.resize(n+1,vector<vector<TreeNode*>>(n+1)); //2 记忆化添加得代码
if(n == 0) return {};
return generateTrees(1,n);
}
};
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (root == NULL) return true;
queue<TreeNode*> que;
que.push(root->left);
que.push(root->right);
while (!que.empty()) {
TreeNode* leftNode = que.front(); que.pop();
TreeNode* rightNode = que.front(); que.pop();
if (!leftNode && !rightNode) {
continue;
}
if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
return false;
}
que.push(leftNode->left);
que.push(rightNode->right);
que.push(leftNode->right);
que.push(rightNode->left);
}
return true;
}
};
