Luna Tech

Tutorials For Dummies.

Binary Tree (1)

2021-08-08

0. 前言

Reference: 手把手带你刷二叉树（第一期） - labuladong 的算法小抄 (gitbook.io)

为什么要先刷二叉树？

因为很多经典的算法，包括回溯（Backtracking Algorithm）、动态规划（Dynamic Programming）、分治算法（Divide-and-conquer Algorithm）都是树的问题。

有人说五大常用算法是：动态规划算法，分治算法，回溯算法、贪心算法（Greedy Algorithm）以及分支限界算法（Branch and bound Algorithm）。

所有树的问题都跟树的递归遍历框架代码息息相关，二叉树相关的题目能帮助我们练好递归基本功和框架思维，而递归是学好算法的基本功，所以我们应该先刷二叉树的题目。

换言之，只要涉及递归，都可以抽象成二叉树的问题。

/* 二叉树遍历框架 */
void traverse(TreeNode root) {
    // 前序遍历（在调用所有递归function之前）
    traverse(root.left)
    // 中序遍历（在调用了一个递归function之后）
    traverse(root.right)
    // 后序遍历（在调用了所有递归function之后）
}

两种遍历框架：

相关题目

226. 翻转二叉树 - 力扣（LeetCode） (leetcode-cn.com)

114. 二叉树展开为链表 - 力扣（LeetCode） (leetcode-cn.com)

116. 填充每个节点的下一个右侧节点指针 - 力扣（LeetCode） (leetcode-cn.com)

1. 二叉树递归遍历框架的重要性

快速排序（Quicksort）和归并排序（Mergesort）这两种算法可以理解为：

为什么呢？

快速排序的代码框架

快速排序的逻辑：

注意： nums[lo...p-1] 小于等于 nums[p] 这个条件可以保证和 nums[p] 相等的元素都放在左边的 array 里面。

void sort(int[] nums, int lo, int hi) {
    /********************** 前序遍历位置 *********************/
    /* 假定我们有个 partition function，通过交换元素构建分界点 p */
    int p = partition(nums, lo, hi);
    /*******************************************************/

    sort(nums, lo, p - 1);
    sort(nums, p + 1, hi);
}

先构造分界点，然后再把问题分解成左右子数组两个小问题，分别构造子分界点，持续递归遍历。

这就是二叉树前序遍历的应用。

归并排序的代码框架

归并排序的逻辑：

void sort(int[] nums, int lo, int hi) {
    int mid = (lo + hi) / 2;
    sort(nums, lo, mid);
    sort(nums, mid + 1, hi);

    /****** 后序遍历位置 ******/
    /* 合并两个排好序的子数组  */
    merge(nums, lo, mid, hi);
    /************************/
}

先分成左右子数组，分别排序，然后合并起来，这就是分治算法。

根据 merge 的调用位置，我们可以发现这是二叉树后序遍历的应用。

2. 写递归算法的秘诀

写递归算法的关键是要明确函数的「定义」是什么，然后相信这个定义，利用这个定义推导最终结果，绝不要跳入递归的细节。

初学者学递归最容易犯的错误就是跳进递归里面出不来（我也是，经常把自己搞晕）。

但是我们换个思路，递归其实就是数学归纳法的应用，已知 k = 1 的时候如何，k = 2 的时候如何，k = n 的时候如何。

我们不需要再次去证明这个公式，只需要搞清楚函数的定义，并且使用这个函数就行了。

举例：计算二叉树一共有几个节点

这道题很简单，root + 左右子树的节点就是总节点数。

// 定义：count(root) 返回以 root 为根的树有多少节点
int count(TreeNode root) {
    // base case
    if (root == null) return 0;
    // 自己加上子树的节点数就是整棵树的节点数
    return 1 + count(root.left) + count(root.right);
}

那么如何计算左右子树的节点数呢？

和整棵树一样，root’ + 左右子树’ 的节点数。

这就是递归的思维了。

写树相关的算法/递归算法，简单说就是，先搞清楚当前 root 节点「该做什么」以及「什么时候做」，然后根据函数定义递归调用子节点，递归调用会让子节点做相同的事情。

3. 题目实战

226. 翻转二叉树

226. 翻转二叉树

输入：二叉树节点 root

输出：镜像翻转的二叉树节点 root

思路：把每个节点的左右节点互换

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
      	// 特殊 case
        if (root == null)
            return null;
        // 前序遍历，左右互换
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        // 进入递归，左右子树重复操作
        invertTree(root.left);
        invertTree(root.right);
        // 返回结果
        return root;
    }
}

其他解法

我们是否可以使用后序遍历来完成这个题目呢？

答案是：可以，前序和后序在这个题目里面不重要，只要两个 invertTree 放在一起就行了。

class Solution {
    public TreeNode invertTree(TreeNode root) {
      	// 特殊 case
        if (root == null)
            return null;
        // 进入递归，左右子树重复操作
        invertTree(root.left);
        invertTree(root.right);
        // 后序遍历，左右互换
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        // 返回结果
        return root;
    }
}

我们是否可以用中序遍历来完成这个题目呢？

答案是：可以，但是得改动。

假如你按照之前的代码，只是换个位置的话，root.right 其实在进行第二次递归的时候已经变成了 root.left。

// not working
class Solution {
    public TreeNode invertTree(TreeNode root) {
      	// 特殊 case
        if (root == null)
            return null;
        // 进入递归，左子树重复操作
        invertTree(root.left);
        // 中序遍历，左右互换
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        // 进入递归，右子树重复操作
        invertTree(root.right);

        // 返回结果
        return root;
    }
}

所以呢，假如你要用中序遍历，得把 invertTree(root.right); 改成 invertTree(root.left);

class Solution {
    public TreeNode invertTree(TreeNode root) {
      	// 特殊 case
        if (root == null)
            return null;
        // 进入递归，左子树重复操作
        invertTree(root.left);
        // 中序遍历，左右互换
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        // 进入递归，右子树重复操作
        invertTree(root.left); // 注意这里的 node 实际上是之前的 right
        // 返回结果
        return root;
    }
}

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

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

这道题目要求我们把每一层的左右节点联系起来。

root.left.next = root.right; 就是我们的核心逻辑；

那我们想到的第一个解法可能是这样的：

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public 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 连起来啊！因为它俩不属于一个子树。

那怎么办呢？

我们要利用节点 2 和 3 之间的关系，已知 root.left.next = root.right;，那么 root.left.right.next = root.left.next.left; 就可以建立两个子树之间的关系了。

但是我们要怎么用递归的方式来抽象出这个逻辑呢？

我们可以通过写一个辅助 function，输入两个节点（左右子树 root），然后把这两个节点的子树 node 之间建立联系，也就是把「每一层二叉树节点连接起来」这个问题抽象成「将每两个相邻节点都连接起来」：

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    // 主函数
    public 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. 二叉树展开为链表

Ref: labuladong

思路：从最小 case 开始考虑，当 root 只有一个左节点和一个右节点的时候，我们需要把左节点变成右节点，再把原右节点变成新右节点的右节点。

这段代码可以表示为：

TreeNode orgRight = root.right;
root.right = null;
root.right = root.left;
root.right.right = orgRight;

那么，假设 root.left 和 root.right 都是经过 flatten 之后的结果，我们只需要最后返回 root 即可。

PS: 题目给的 method 是 void type，所以我们不需要 return root，只需要 return 就可以了（有点绕）。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // 定义：将以 root 为根的树拉平为链表
    public void flatten(TreeNode root) {
        // base case, 根据题目示例2来写
        if (root == null) return;
				// flatten both left and right trees
        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) {
            p = p.right;
        }
        p.right = right;
    }
}

为什么要做后序遍历呢？

因为我们的假设是 root.left 和 root.right 都已经经过 flatten 了，所以我们只需要关注如何把最小 case 的节点进行 flatten 即可。

假如我们要做前序遍历的话，调用 flatten 递归的时候 root.left 和 root.right 需要指向最初的那两个 node。

class Solution {
    public void flatten(TreeNode root) {
        // base case
        if (root == null) return;

        /**** 前序遍历 ****/
        // 1、储存最初的左右节点
        TreeNode left = root.left;
        TreeNode right = root.right;

        // 2、进行第一步 flatten 操作（左子树）
        root.left = null;
        root.right = left;

        // 3、进行第二步 flatten 操作（右子树）
        TreeNode p = root;
        while (p.right != null) {
            p = p.right;
        }
        p.right = right;

        // 调用递归（使用未经改变的两个节点）
        flatten(left);
        flatten(right);
    }
}