二叉树开展为链表

题目形容

题目链接：https://leetcode-cn.com/probl…

给你二叉树的根结点 root，请你将它开展为一个单链表：

开展后的单链表应该同样应用 TreeNode，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null。
开展后的单链表应该与二叉树 先序遍历 程序雷同。

后序遍历原地批改法

思路：因为程序必须依照先序遍历，为了不便进行结点的记录和左右子树链接的批改，能够用后序遍历的办法，如果用先序遍历，则以后结点的下一结点较难判断，将以后结点传至下一次递归中的做法也很麻烦。而后续遍历中，只需用一个 last 结点记录以后结点的下一个结点，按后序遍历记录，能够使得代码很清晰。

TreeNode* last = nullptr;
    void flatten(TreeNode* root) {if(!root)return;
        flatten(root->right);
        flatten(root->left);
        root->right = last;
        root->left = nullptr;
        last = root;
    }                                                                                                                                

二叉树最大门路和

题目形容

题目链接：https://leetcode-cn.com/probl…
门路 被定义为一条从树中任意节点登程，沿父节点 - 子节点连贯，达到任意节点的序列。同一个节点在一条门路序列中 至少呈现一次。该门路 至多蕴含一个 节点，且不肯定通过根节点。

门路和 是门路中各节点值的总和。

给你一个二叉树的根节点 root，返回其 最大门路和。

示例 1：

输出：root = [1,2,3]
输入：6
解释：最优门路是 2 -> 1 -> 3，门路和为 2 + 1 + 3 = 6

递归法思路

二叉树的题，其中一个较惯例的思路就是递归法。尤其是这种算最大最小值的题，非常适合用递归来解决。但这题非凡的一个点在于：门路并不仅限于从根到子节点，而能够从一个节点到另一个节点。初看起来非常复杂，用递归思路又不可行了，但当你画一棵较为简单的树，本人比划比划其中可能的门路时就会发现，事实上可能存在的门路并没有那么多。这题最困扰人的一点就是门路能够从一个节点的左子树走到该结点的右子树，因而使人感觉可能性太多，极难穷举。但本人画过一遍后能够发现，一旦你所画的门路中同时蕴含了一个节点的左子树和右子树及其自身，这条门路就没法回溯到上一层了；如果想要回溯到上一层，就只能是走其中一个子树。
看清了这一点，就能够得出一个论断：
对于任意一个节点, 如果最大和门路蕴含该节点, 那么只可能是两种状况:

1. 其左右子树中所形成的和门路值较大的那个加上该节点的值后向父节点回溯形成最大门路
2. 左右子树都在最大门路中, 加上该节点的值形成了最终的最大门路

这样，递归法就很好做了：

class Solution {
public:
    int ans = INT_MIN;
    int countSum(TreeNode* root) {if(!root) return 0;
        int leftMax = max(countSum(root -> left),0);
        int rightMax = max(countSum(root -> right),0);
        ans = max(ans, leftMax+rightMax+root->val);
        return max(leftMax,rightMax) + root->val;
    }
    int maxPathSum(TreeNode* root) {countSum(root);
         return ans;
    }
};