纲领篇总结的二叉树解题总纲：

二叉树解题的思维模式分两类： 1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现，这叫「遍历」的思维模式。 2、是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫「分解问题」的思维模式。 无论使用哪种思维模式，你都需要思考： 如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？其他的节点不用你操心，递归函数会帮你在所有节点上执行相同的操作。

226. 翻转二叉树

遍历解法

这题能不能用「遍历」的思维模式解决？
可以，我写一个 traverse 函数遍历每个节点，让每个节点的左右子节点颠倒过来就行了。
单独抽出一个节点，需要让它做什么？让它把自己的左右子节点交换一下。
需要在什么时候做？好像前中后序位置都可以。

public TreeNode invertTree(TreeNode root) {
    traverse(root);
    return root;
}
void traverse(TreeNode root){
    if(root == null)
        return;
    //前序位置
    //将当前节点的左右子节点互换
    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;
    //中序位置
    traverse(root.left);
    //后序位置
    traverse(root.right);
}

分解解法

我们尝试给 invertTree 函数赋予一个定义：

// 定义：将以 root 为根的这棵二叉树翻转，返回翻转后的二叉树的根节点 
TreeNode invertTree(TreeNode root);

然后思考，对于某一个二叉树节点 x 执行 invertTree(x)，你能利用这个递归函数的定义做点啥？
我可以用 invertTree(x.left) 先把 x 的左子树翻转，再用 invertTree(x.right) 把 x 的右子树翻转，最后把 x 的左右子树交换，这恰好完成了以 x 为根的整棵二叉树的翻转，即完成了 invertTree(x) 的定义。
直接写出解法代码：

// 定义：将以 root 为根的这棵二叉树翻转，返回翻转后的二叉树的根节点
TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    // 利用函数定义，先翻转左右子树
    TreeNode left = invertTree(root.left);
    TreeNode right = invertTree(root.right);
    // 然后交换左右子节点
    root.left = right;
    root.right = left;
    // 和定义逻辑自恰：以 root 为根的这棵二叉树已经被翻转，返回 root
    return root;
}

这种「分解问题」的思路，核心在于你要给递归函数一个合适的定义，然后用函数的定义来解释你的代码；如果你的逻辑成功自恰，那么说明你这个算法是正确的。

116. 填充每个节点的下一个右侧节点指针

遍历解法

很显然，一定可以。
每个节点要做的事也很简单，把自己的 next 指针指向右侧节点就行了。

但是需要注意的是，node5 和 node6 是两个父节点不同但是连接起来，其他连接起来的两个节点的父节点都是相同的，比如 node4 和 node5。所以我们要在代码中去强调这一点。

之前的 traverse 函数，遍历的是二叉树的节点。现在我们把二叉树抽象成三叉树，三叉树上的每个节点是二叉树上两个相邻节点。

public Node connect(Node root) {
    if(root == null) return null;
    traverse(root.left, root.right);
    return root;
}
void traverse(Node node1, Node node2){
    if(node1 == null || node2 == null) return;
    //前序位置
    //连接两个二叉树节点
    node1.next = node2;
    //连接相同父节点的两个子节点
    traverse(node1.left, node1.right);
    traverse(node2.left, node2.right);
    //连接不同父节点的两个子节点
    traverse(node1.right, node2.left);
}

这样的 traverse 函数，遍历了整个三叉树，把所有相邻的节点都连接了起来。

分解解法

没有什么好的idea。

114. 二叉树展开为链表

遍历解法

题目说了要的是前序遍历顺序的链表，所以乍一看感觉是可以的：对整棵树进行前序遍历，一遍遍历一遍构造出一条「链表」就行。

// 虚拟头节点，dummy.right 就是结果
TreeNode dummy = new TreeNode(-1);
// 用来构建链表的指针
TreeNode p = dummy;

void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    // 前序位置
    p.right = new TreeNode(root.val);
    p = p.right;

    traverse(root.left);
    traverse(root.right);
}

但是我们注意到 「flatten」函数的返回类型是 void，题目希望我们在原地把二叉树拉平成链表，这样一来就没有用简单的二叉树遍历来解决这道题目。

分解解法

我们尝试给 「flatten」 函数赋予一个定义：

// 定义：输入节点 root，然后 root 为根的二叉树就会被拉平为一条链表
void flatten(TreeNode root);

然后思考，对于某一个二叉树节点 x 执行 flatten(x)，你能利用这个递归函数的定义做点啥？如何按照题目要求把一棵树拉平成一条链表？
对于一个二叉树节点x，可以执行以下流程：
1、先利用 flatten(x.left) 和 flatten(x.right) 将 x 的左右子树拉平
2、将 x 的右子树接到左子树下方，然后将整个左子树作为右子树

这样，以 x 为根的整棵二叉树就被拉平了，恰好完成了「flatten(x)」的定义。
这就是递归的魅⼒，你说 flatten 函数是怎么把左右⼦树拉平的？
不容易说清楚，但是只要知道 flatten 的定义如此并利⽤这个定义，让每⼀个节点做它该做的事情，然后
flatten 函数就会按照定义⼯作。

//定义：给flatten函数输入一个节点root，那么以root为根的二叉树就会被扯平为一条链表
public void flatten(TreeNode root) {
    //base case
    if(root == null) return;

    //将root的左子树和右子树拉平
    flatten(root.left);
    flatten(root.right);

    //后序位置
    //1、左右子树已经被拉平成一条链表
    TreeNode left = root.left;
    TreeNode right = root.right;

    //2、将左子树作为右子树
    root.left = null;
    root.right = left;

    //3、将原先的右子树接到当前右子树的末端
    TreeNode p = root;
    while(p.right != null){//找到当前root的右子树的叶子节点
        p = p.right;
    }
    p.right = right;//找到叶子节点之后将拉平的右子树接上去

}

剑指 Offer 27. 二叉树的镜像

leetcode 226同题。