二叉树定义
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){}
};
二叉树遍历
后序遍历
if(root==nullptr)return;
dfs(root->left);
dfs(root->right);
res.push_back(root->val);
中序遍历
if(root==nullptr)return;
dfs(root->left);
res.push_back(root->val);
dfs(root->right);
先序遍历
if(root==nullptr)return;
res.push_back(root->val);
dfs(root->left);
dfs(root->right);
层级遍历
if(root==null)return;
q;
q.add(root);
while(q不空){
int size=q.size();
for(int i=0;i<size;i++){
q.pop();
if(q.left)q.add(q.left);
if(q.right)q.add(q.right);
}之字打印二叉树：
中序遍历后按层反转vector
二叉搜索树转循环链表：//二叉搜索树转双向循环链表(中序遍历)
vector<Node*> list; // 创建一个列表来保存中序遍历的节点
dfs(root, list); // 执行中序遍历，并将节点添加到列表中
n = list.size(); // 获取列表中节点的数量
if (n == 0) return nullptr; // 如果列表为空，则返回空指针
// 将列表中的节点连接成双向循环链表
for (int i = 0; i < n; ++i) {
list[i]->left = list[(i - 1 + n) % n]; // 设置左指针为前一个节点
list[i]->right = list[(i + 1) % n]; // 设置右指针为后一个节点
}
return list[0]; // 返回链表的头节点（双向循环链表的任意节点都可以作为头节点）
二叉树的最大路径和(*):路径为一条从树中任意节点出发,达到任意节点的序列(不一定经过根节点)
为了便于理解，给出示例。
class Solution {
private:
int maxSum; // 全局变量，记录最大路径和
// 辅助函数，返回以当前节点为根的子树中的最大路径和
int dfs(TreeNode* root) {
if (root == nullptr) return 0;
// 递归计算左子树和右子树的最大路径和
int leftSum = max(dfs(root->left), 0);
int rightSum = max(dfs(root->right), 0);
// 计算经过当前节点的最大路径和，并更新全局最大路径和
int currSum = root->val + leftSum + rightSum;
maxSum = max(maxSum, currSum);
// 返回以当前节点为根的子树中的最大路径和（注意：这里只考虑经过当前节点的路径）
return root->val + max(leftSum, rightSum);
}
public:
int maxPathSum(TreeNode* root) {
maxSum = INT_MIN; // 初始化最大路径和为最小整数值
dfs(root); // 从根节点开始深度优先搜索
return maxSum; // 返回最大路径和
}
}; 二叉树路径和的所有方案??：
List<List>res;
List path;
List<List<Integer>> pathSum(root,target):
dfs(root,0,target);
//初始时sum和root的关系是异步,且root优先于sum
//终止必须在叶子节点，否则会有重复方案
void dfs(root,sum,target)
if root叶子节点:
if sum+root.val==target:
path.add(root.val);
res.add(new ArrayList<>(path));//注意写法
path.remove(path.size()-1);
path.add(root.val);
if(root.left!=null)
dfs(root.left,sum+root.val,target);
if(root.right!=null)
dfs(root.right,sum+root.val,target);
path.remove(path.size()-1)
判断对称二叉树
// 判断两棵树是否对称
bool isSymmetric(TreeNode* l, TreeNode* r)
// 如果两个节点都为空，则是对称的
if (l 空&& r空)return true;
// 如果只有一个节点为空，或者两个节点都不为空但值不相等，则不是对称的
if (l == nullptr || r == nullptr || l->val != r->val)return false;
// 递归判断左子树和右子树是否对称
return isSymmetric(l->left, r->right) && isSymmetric(l->right, r->left);
// 判断一棵二叉树是否是对称二叉树
bool isSymmetric(TreeNode* root) {
// 空树是对称的
if (root == nullptr) return true;
// 对于非空树，只需要判断根节点的左右子树是否对称
return isSymmetric(root->left, root->right);
} 时间复杂度是 O(n)，因为需要遍历二叉树的每个节点一次。在递归过程中，对每个节点的左子树和右子树进行对称性的比较。对于每个节点，进行常数时间的值比较，并递归地检查其子节点。由于每个节点只会被访问一次，时间复杂度是线性的。
判断平衡二叉树
// 计算树的高度
h(root):
if root == null:
return 0
return 1 + max(h(root.left), h(root.right))
// 判断平衡二叉树
isB(root):
if root == null:
return true
return abs(h(root.left) - h(root.right)) <= 1 && isB(root.left) && isB(root.right)
判断是否是相同的树
// 判断两个树是否相同
isSame(p, q):
// 如果两个树都为空，则它们是相同的
if p is null and q is null:
return true
// 如果一个树为空而另一个不为空，或者它们的根节点值不相等，则它们不是相同的树
if p is null or q is null or p.val != q.val:
return false
// 递归地检查左子树和右子树是否相同
return isSame(p.left, q.left) and isSame(p.right, q.right)时间复杂度O(n)
合并二叉树：
两个二叉树对应位置相加，如果有一个为空视为0，返回新的二叉树
function mergeTrees(root1, root2):
// 创建一个新的根节点，初始值为0
root = new TreeNode(0)
// 如果两个根节点都为空，则返回空
if root1 is null and root2 is null:
return null
// 如果root1为空，返回root2
if root1 is null:
return root2
// 如果root2为空，返回root1
if root2 is null:
return root1
// 合并两个根节点的值
root.val = root1.val + root2.val
// 递归地合并左子树和右子树
root.left = mergeTrees(root1.left, root2.left)
root.right = mergeTrees(root1.right, root2.right)
// 返回合并后的新树的根节点
return root左叶子之和：
带标记信息的dfs：用flag标记当前节点是父节点的左节点还是右节点，1左2右
sum(root):
return dfs(root,0)
dfs (root, flag):
if(root==null) return 0
if(root.left==null&&root.right==null&&flag==1)return root.val;
return dfs(root.left,1)+dfs(root.right,2);最大深度
D(root):
root==null return 0
return max(D(left),D(right))+1最小深度：最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
需要讨论三种特殊情况注意
答案为5。
D(root):
root空 return 0
左空右不空 return D(right)+1
右空左不空 return D(left)+1
return min(D(left),D(right))+1最近公共祖先
find(root,p,q)
//p,q直接是root
root=null||root=p||root=q return root;
left=find(root.left,p,q)
right=find(root.right,p,q)
左子树找不到返回right
if left=null:return right
右子树找不到返回left
if right=null:return left
p,q在root两侧返回root
return root 构建二叉树
build(nums,int l,int r):
nums：i为根节点,左区间构造左子树,右区间构造右子树
if(l>r)return null;
TreeNode root=new nums[i]
root.left=build(nums,l,i-1)
root.right=build(nums,i+1,r)
return root
由有序数组构造高度平衡的二叉搜索树
build nums,l,r:
if l>r return;
root=new nums[mid]//使用中间的数构造
root.left=build(nums,l,mid-1)
root.right=build(nums,mid+1,r)
return root由前序遍历和中序遍历构建二叉树
前序遍历:根[左][右]
中序遍历:[左]根[右]
map存索引,中序找根,求左区间长度
map[vin[i]] = i
//在中序遍历中迅速找到根节点,可以使用哈希表
build(pre,l1,r1,vin,l2,r2):
if r1>l1||r2>l2:return
root=new pre[l1];
int idx=map[pre[l1]]
int len=idx-1-l2+1;
root.left=build(pre,l1+1,l1+1+len-1,vin,l2,idx-1);
root.right=build(pre,l1+l+len-1+1,r1,vin,idx+1,r2);树的子结构：
isSubTree(A,B)://判断B是否是A的子结构
思路：先序遍历A,每个节点分别判断以B为根的树是否是该树的子树
//如果B是null或者A是null
if(A==null||B==null)return false
//判断以B为根的树是否是以A为根的树的子树
dfs(A,B)|| isSubTree(A.left,B) || isSubTree(A.right,B)
dfs(A,B):
if(B==null)return true
if(A==null)return false
return A.val==B.val&&dfs(A.left,B.left)&&dfs(A.right,B.right)输入：root = [1,2,3]。输出：25。从根到叶子节点路径 1->2 代表数字 12。从根到叶子节点路径 1->3 代表数字 13。数字总和 = 12 + 13 = 25。
root,sum表示[已经]遍历root节点所有sum的值？？？
dfs(root,sum):
叶子节点为空,0；
只有叶子节点sum*10+root->val;
return dfs(root.left,sum*10+root.left.val)+dfs(root.right,sum*10+root.right.val);判断完全二叉树
???
在所有叶子节点下补上两个null.
while:q
t=q.poll
if(t==null)continue;
else
q.add(t.left);
q.add(t.right);
完全二叉树:所有叶子节点补上Null之后,层序遍历中一定满足非空节点在左面，空节点在右面。
如果非空节点中有一个空节点，那么不是完全二叉树。可以用list(0|1)+双指针实现。
判断二叉搜索树
bool isValidBST(TreeNode* root, long long min_val = LONG_MIN, long long max_val = LONG_MAX) {
if (root == NULL) return true; // 空树是有效的
if (root->val <= min_val || root->val >= max_val) return false; // 当前节点值超出范围
// 递归检查左右子树
return isValidBST(root->left, min_val, root->val) && isValidBST(root->right, root->val, max_val);
}
中序遍历有序；list存放中序遍历的序列
二叉搜索树下一个节点:
如果root.val<=p.val说明下一个节点一定在root右子树中
否则节点要么 在左子树中，要么是root
dfs(root,p):
if root==null:return null
if(root.val<=p.val)dfs(root.right,p);
TreeNode node=dfs(root.left,p);
return node==null?root:node;二叉搜索树的插入
insert(root,val):
root==null return new root(val)
if root.val>val: root.left=insert(root.left,val);
else root.right=insert(root.right,val);
return root二叉搜索树的搜索
search(root,val):
if root==null: return null
if root.val==val:return root;
else root.val>val: search(root.left,val);
else root.val<val: search(root.right,val);二叉搜索树第k大节点： 后序遍历k次停下返回
dfs(root):
if(root==nullptr)return;
dfs(root.right);
cnt++;
if(cnt==k){
res=root.val;
return;
}
dfs(root.left);二叉搜索树转平衡二叉树
传入0,n-1
中序遍历然后对这个有序序列递归建树，
left= l,mid-1
right=mid+1,r
root=mid二叉搜索树转换为累加数：BST节点的权值变为大于等于节点权值之和
节点的权值变为中序遍历的后缀和，即右中左序列的前缀和
int pre = 0; // 记录前一个节点的数值
void traversal(TreeNode* cur):
// 右中左遍历
if (cur == NULL)return;
traversal(cur->right);
cur->val += pre;
pre = cur->val;
traversal(cur->left);修剪二叉搜索树：
删除节点使BST所有节点都在[low,high]范围内:
trim(root,low,high)：
if root.val>high://删除右子树
root=root.left
return trim(root,low,high)
else if root.val<low://删除左子树
root=root.right
return trim(root,low,high)
else://对左子树和右子树修剪
root.left=trim(root.left,low,high)
root.right=trim(root.right,low,high)
return root
二叉搜索树的删除:
//不等于在左右子树中删除
//等于如果左右子树不全为空,返回另一颗子树
//如果全部为空,找右子树的最左叶子节点node
delete(root,val):
if root=null return null;
if root.val>val root.left=delete(root.left,val);
else if root.val<val root.right=delete(root.right,val);
else
if root.left=null return root.right
if root.right=null return root.left
TreeNode t=root.right;
while(t.left!=null)t=t.left;
t.left=root.left;
root=root.right;
return root
LeetCode 226 翻转二叉树
/**
* 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* invertTree(TreeNode* root) {
//递归出口
if(root==NULL)
return NULL;
if(!root->left&&!root->right)
{
return root;
}
//递归体
TreeNode *l=invertTree(root->left);//递归翻转左子树，返回翻转后 左子树的根节点
TreeNode *r=invertTree(root->right);//递归翻转右子树,返回翻转后 右子树的根节点
root->right=l;
root->left=r;
return root;
}
};LeetCode 114 二叉树展开为链表
class Solution {
public:
void flatten(TreeNode* root) {
if(root==NULL||!root->left&&!root->right)
{
return;
}
TreeNode *l=root->left;
flatten(l);
TreeNode *r=root->right;
flatten(r);
root->left=NULL;
root->right=l;
TreeNode *p=l;
if(p)
{
while(p->right)
{
p=p->right;
}
p->right=r;
}
else
{
root->right=r;
}
return ;
}
};