死磕二叉树
✏️ 1、DFS深度遍历 & 递归
DFS深度遍历 & 递归给定一个非空二叉树，返回其最大路径和。本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
路径每到一个节点，有 3 种选择： 停下不走。 走到左子节点。 走到右子节点。走到子节点，又面临这 3 种选择。于是有了递归的思路。 不能走进一个分支，又掉头走另一个分支，不符合要求。
定义递归函数
我们关心：如果路径走入一个子树，能从中捞取的最大收益，不关心具体怎么走。 这是一种属于递归的、自顶而下的思考方式。
定义
dfs函数：返回当前子树能向父节点 “提供” 的最大路径和。向下：即，一条从父节点延伸下来的路径，能在当前子树中获得的最大收益。它分为三种情况，取其中最大的： 停在当前子树的 root，收益：root.val。 走入左子树，最大收益：
root.val + dfs(root.left)。 走入右子树，最大收益：root.val + dfs(root.right)。 当遍历到 null 节点时，收益为 0，所以返回 0。向上：如果一个子树提供的「最大路径和」为负，如下图。路径走入它，收益不增反减，我们希望这个子树完全不被考虑，所以让它返回 0，成为死支。
int helper(TreeNode *node, int &sum){
if(!node){
sum = max(sum, 0);
return 0;
}
int lsum = 0, rsum = 0;
if(node->left){
lsum = max(0, helper(node->left, sum)); // 左子树的贡献
}
if(node->right){
rsum = max(0, helper(node->right, sum)); // 右子树的贡献
}
sum = max(sum, node->val + lsum + rsum); // 当前子树的 maxSum 挑战最大值
return node->val + max(lsum, rsum); // 向父节点提供的最大和，要包括自己
}
int maxPathSum(TreeNode* root){
int maxSum = INT_MIN;
helper(root, maxSum);
return maxSum;
}给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。（分治）
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。（回溯）
思路一：迭代，后续遍历，PATH数组和栈同步，到叶节点判断当前路径是否满足，满足就将PATH加到结果中。
思路二：递归，
✏️ 2、LCA问题
LCA问题给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。经典的LCA（Least Common Ancestors）问题。
思路一、后序遍历：因为后序遍历的栈中始终存放着当前要访问节点的祖先节点。所以两次后序遍历，分别遍历到两个节点位置结束，然后两个栈分别保存两个节点的祖先节点，依次弹栈，遇到第一个相同的节点即可。（最应该想到的解法）
思路二、递归：
思路三、倍增法：
思路四、欧拉序+ST表：
思路五、
Tarjan算法：
思路一、后序遍历：因为后序遍历的栈中始终存放着当前要访问节点的祖先节点。所以两次后序遍历，分别遍历到两个节点位置结束，然后两个栈分别保存两个节点的祖先节点，依次弹栈，遇到第一个相同的节点即可。（最应该想到的解法）
思路二、递归：
思路三、倍增法：
思路四、欧拉序+ST表：
思路五、
Tarjan算法：
拓展：
✏️ 3、序列化和反序列化
思路一：BFS 序列成对应的完全二叉树（超时，主要是字符串
split耗时长）。思路二：DFS 前中后序都可以，递归实现。
思路三：改进的BFS，不是完全二叉树，而是扩展二叉树的叶子节点为NULL节点。
思路四：类似于官方题解方法二，用分隔符包装。
✏️ 4、二叉树遍历之Morris算法
✏️ 5、镜像问题
5.1、二叉树的镜像
5.2、判断二叉树是不是对称二叉树
5.3、求X节点的个数（阿里面试题）
5.4、判断两棵二叉树是否同构
同构是指：两课树可以通过有限次变换左右子树变为同一棵树。如图：
✏️ 6、其他
6.1、逆时针打印完全二叉树的边界节点
完全二叉树用数组存储，从根节点开始逆时针打印完全二叉树的边界节点。
最后更新于
这有帮助吗？