前言

相信如果你看过前面几篇，那对下面这几题应该是游刃有余

深入理解二叉树的前中后序

后序技巧，轻松解决三道题，二叉树的最大深度、直径、最大路径和

226. 翻转二叉树

226. 翻转二叉树，leetcode链接

函数签名如下：

public TreeNode invertTree(TreeNode root) {
    };

输入一个二叉树根节点root，让你把整棵树镜像翻转，比如输入的二叉树如下：

通过观察，我们发现只要把二叉树上的每一个节点的左右子节点进行交换，最后的结果就是完全翻转之后的二叉树。

可以直接写出解法代码：

// 将整棵树的节点翻转
TreeNode invertTree(TreeNode root) {
    
    // base case
    if (root == null) return null;

    /**** 前序遍历位置 ****/
    // root 节点需要交换它的左右子节点
    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;

    // 让左右子节点继续翻转它们的子节点
    invertTree(root.left);
    invertTree(root.right);

    return root;
}

思路在于我们发现翻转整棵树就是交换每个节点的左右子节点，于是我们把交换左右子节点的代码放在了前序遍历的位置。

值得一提的是，如果把交换左右子节点的代码放在后序遍历的位置也是可以的，但是放在中序遍历的位置是不行的，为什么？自己体会

其实这里还有另一种写法，就是使用分解子问题的思路：

// 定义：将以 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. 填充二叉树节点的右侧指针

116. 填充每个节点的下一个右侧节点指针，leetcode链接

函数签名如下：

public Node connect(Node root) {
    };

题目的意思就是把二叉树的每一层节点都用next指针连接起来：

而且题目说了，输入是一棵「完美二叉树」，形象地说整棵二叉树是一个正三角形，除了最右侧的节点next指针会指向null，其他节点的右侧一定有相邻的节点。

这道题怎么做呢？把每一层的节点穿起来，是不是只要把每个节点的左右子节点都穿起来就行了？

我们可以模仿上一道题，写出如下代码：

Node connect(Node root) {
    
    if (root == null || root.left == null) return root;

    root.left.next = root.right;

    connect(root.left);
    connect(root.right);
    return root;
}

这样其实有很大问题，再看看这张图：

节点 5 和节点 6 不属于同一个父节点，那么按照这段代码的逻辑，它们两个就没办法被穿起来，这是不符合题意的。

其实二叉树问题的难点在于，如何把题目的要求细化成每个节点需要做的事情，但是如果只依赖一个节点的话，肯定是没办法连接「跨父节点」的两个相邻节点的。

那么，我们的做法就是增加函数参数，一个节点做不到，我们就给他两个节点，「将每一层二叉树节点连接起来」可以细化成「将每两个相邻节点都连接起来」：

// 主函数
Node connect(Node root) {
    
    if (root == null) return null;
    connectTwoNode(root.left, root.right);
    return root;
}

// 定义：输入两个节点，将它们两个连接起来
void connectTwoNode(Node node1, Node node2) {
    
    if (node1 == null || node2 == null) return;

    /**** 前序遍历位置 ****/
    // 将传入的两个节点连接
    node1.next = node2;

    // 连接相同父节点的两个子节点
    connectTwoNode(node1.left, node1.right);
    connectTwoNode(node2.left, node2.right);
    // 连接不同父节点的两个子节点
    connectTwoNode(node1.right, node2.left);
}

这样，connectTwoNode函数不断递归，可以无死角覆盖整棵二叉树，将所有相邻节点都连接起来，也就避免了我们之前出现的问题。

114. 将二叉树展开为链表

114. 二叉树展开为链表，leetcode链接

函数签名如下：

public void flatten(TreeNode root) {
    

我们先理解这个函数的定义：

给flatten函数输入一个节点root，那么以root为根的二叉树就会被拉平为一条链表。

我们再梳理一下，如何按题目要求把一棵树拉平成一条链表？很简单，以下流程：

1. 将root的左子树和右子树拉平，

2. 将root的左子树插入到右子树的地方

3. 然后将原来的右子树接到左子树的最右边节点

上面三步看起来最难的应该是第一步，如何把root的左右子树拉平？

其实很简单，按照flatten函数的定义，对root的左右子树递归调用flatten函数即可：

// 定义：将以 root 为根的树拉平为链表
void flatten(TreeNode root) {
    
    // base case
    if (root == null) return;

    flatten(root.left);
    flatten(root.right);

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

    // 2、将root的左子树插入到右子树的地方
    root.left = null;
    root.right = left;

    // 3、将原来的右子树接到左子树的最右边节点
    TreeNode cur = root;
    while (cur.right != null) {
    
        cur = cur.right;
    }
    cur.right = right;
}

看，这就是递归的魅力，你说flatten函数是怎么把左右子树拉平的？

不太容易说清楚，但是我只要知道flatten函数的定义如此，要相信这个定义，然后flatten函数就会按照定义工作。