算法思维-二叉树

一纲领

先在开头总结一下，二叉树解题的思维模式分两类：

1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现，这叫「遍历」的思维模式。

2、是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫「分解问题」的思维模式。

1.1 二叉树重要性

举例：快速排序就是个二叉树的前序遍历，归并排序就是个二叉树的后序遍历。

快速排序

快速排序的逻辑是，若要对 nums[lo..hi] 进行排序，我们先找一个分界点 p，通过交换元素使得 nums[lo..p-1] 都小于等于 nums[p]，且 nums[p+1..hi] 都大于 nums[p]，然后递归地去 nums[lo..p-1] 和 nums[p+1..hi] 中寻找新的分界点，最后整个数组就被排序了。


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

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

先构造分界点，然后去左右子数组构造分界点。即是二叉树的前序遍历

归并排序

若要对 nums[lo..hi] 进行排序，我们先对 nums[lo..mid] 排序，再对 nums[mid+1..hi] 排序，最后把这两个有序的子数组合并，整个数组就排好序了。


// 定义：排序 nums[lo..hi]
void sort(int[] nums, int lo, int hi) {
    int mid = (lo + hi) / 2;
    // 排序 nums[lo..mid]
    sort(nums, lo, mid);
    // 排序 nums[mid+1..hi]
    sort(nums, mid + 1, hi);

    /****** 后序位置 ******/
    // 合并 nums[lo..mid] 和 nums[mid+1..hi]
    merge(nums, lo, mid, hi);
    /*********************/
}

先对左右子数组排序，然后合并，是二叉树的后序遍历，也是分治算法。

1.2 理解前中后序

框架如下：


void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    // 前序位置
    traverse(root.left);
    // 中序位置
    traverse(root.right);
    // 后序位置
}

所谓前序位置，就是刚进入一个节点（元素）的时候，后序位置就是即将离开一个节点（元素）的时候。

以数组和链表为例：

前序位置的代码在刚刚进入一个二叉树节点的时候执行；

后序位置的代码在将要离开一个二叉树节点的时候执行；

中序位置的代码在一个二叉树节点左子树都遍历完，即将开始遍历右子树的时候执行。

一个算法中可以同时有前序位置和后续位置的操作。含义就是前序：在进入该节点时执行，后续：离开节点时执行。

1.3 两种解题思路

题目：求二叉树的最大深度。

a. 方案一遍历一次


// 记录最大深度
int res = 0;
// 记录遍历到的节点的深度
int depth = 0;

// 主函数
int maxDepth(TreeNode root) {
	traverse(root);
	return res;
}

// 二叉树遍历框架
void traverse(TreeNode root) {
	if (root == null) {
		return;
	}
	// 前序位置
	depth++;
    if (root.left == null && root.right == null) {
        // 到达叶子节点，更新最大深度
		res = Math.max(res, depth);
    }
	traverse(root.left);
	traverse(root.right);
	// 后序位置
	depth--;
}

前序位置是进入一个节点的时候，depth+1；后序位置是离开一个节点的时候，depth-1；

b. 方案二递归分解问题


// 定义：输入根节点，返回这棵二叉树的最大深度
int maxDepth(TreeNode root) {
	if (root == null) {
		return 0;
	}
	// 利用定义，计算左右子树的最大深度
	int leftMax = maxDepth(root.left);
	int rightMax = maxDepth(root.right);
	// 整棵树的最大深度等于左右子树的最大深度取最大值，
    // 然后再加上根节点自己
	int res = Math.max(leftMax, rightMax) + 1;

	return res;
}

可以通过子树的最大深度推导出原树的深度，所以当然要首先利用递归函数的定义算出左右子树的最大深度，然后推出原树的最大深度，主要逻辑自然放在后序位置。

1.4 后序位置的特殊

求二叉树最长直径长度：所谓二叉树的「直径」长度，就是任意两个结点之间的路径长度。最长「直径」并不一定要穿过根结点


class Solution {
    // 记录最大直径的长度
    int maxDiameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        maxDepth(root);
        return maxDiameter;
    }

    int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftMax = maxDepth(root.left);
        int rightMax = maxDepth(root.right);
        // 后序位置，顺便计算最大直径
        int myDiameter = leftMax + rightMax;
        maxDiameter = Math.max(maxDiameter, myDiameter);

        return 1 + Math.max(leftMax, rightMax);
    }
}

1.5 以树的视角看动态回归、回溯、DFS

动归/DFS/回溯算法都可以看做二叉树问题的扩展，只是它们的关注点不同：

动态规划算法属于分解问题的思路，它的关注点在整棵「子树」。

回溯算法属于遍历的思路，它的关注点在节点间的「树枝」。

DFS 算法属于遍历的思路，它的关注点在单个「节点」。

二思想

💡

二叉树解题的思维模式分两类：

1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现，这叫「遍历」的思维模式。

第二种重点在于对递归函数的定义，然后用定义的函数来解释代码。

2.1 遍历

力扣第 116 题「填充每个二叉树节点的右侧指针open in new window」

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。

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

遍历：每个节点要做的事也很简单，把自己的 next 指针指向右侧节点就行了。

注意：节点 5 和节点 6 不属于同一个父节点，普通遍历无法连接两节点，我们可以在二叉树的基础上进行抽象，你把图中的每一个方框看做一个节点。一棵二叉树被抽象成了一棵三叉树，三叉树上的每个节点就是原先二叉树的两个相邻节点。


// 主函数
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);
}

2.2 递归（分治）

给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

遍历：

注意 flatten 函数的签名，返回类型为 void，也就是说题目希望我们在原地把二叉树拉平成链表。

这样一来，没办法通过简单的二叉树遍历来解决这道题了。

分解问题:

定义flatten函数


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


// 定义：将以 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.left = null;
    root.right = left;

    // 3、将原先的右子树接到当前右子树的末端
    TreeNode p = root;
    while (p.right != null) {
        p = p.right;
    }
    p.right = right;
}

三构造二叉树

二叉树的构造问题一般都是使用「分解问题」的思路：构造整棵树 = 根节点 + 构造左子树 + 构造右子树。

3.1 通过前序和中序数组构造二叉树

经典题目：

先看下两种遍历的数字格式

找到根节点是很简单的，前序遍历的第一个值 preorder[0] 就是根节点的值。

通过「分解问题」的思路：构造整棵树 = 根节点 + 构造左子树 + 构造右子树。

代码框架如下：问题在于分解处理时参数？应该写什么


/* 主函数 */
public TreeNode buildTree(int[] preorder, int[] inorder) {
    // 根据函数定义，用 preorder 和 inorder 构造二叉树
    return build(preorder, 0, preorder.length - 1,
                 inorder, 0, inorder.length - 1);
}

/* 
    build 函数的定义：
    若前序遍历数组为 preorder[preStart..preEnd]，
    中序遍历数组为 inorder[inStart..inEnd]，
    构造二叉树，返回该二叉树的根节点 
*/
TreeNode build(int[] preorder, int preStart, int preEnd, 
               int[] inorder, int inStart, int inEnd) {
    // root 节点对应的值就是前序遍历数组的第一个元素
    int rootVal = preorder[preStart];
    // rootVal 在中序遍历数组中的索引
    int index = 0;
    for (int i = inStart; i <= inEnd; i++) {
        if (inorder[i] == rootVal) {
            index = i;
            break;
        }
    }

    TreeNode root = new TreeNode(rootVal);
    // 递归构造左右子树
    root.left = build(preorder, ?, ?,
                      inorder, ?, ?);

    root.right = build(preorder, ?, ?,
                       inorder, ?, ?);
    return root;
}

对于左右子树对应的 inorder 数组的起始索引和终止索引比较容易确定：

而对于 pre 的边界确认，则是通过中序数组的左子树的节点数推导出来，值为 preStart+leftSize


int leftSize = index - inStart;

root.left = build(preorder, preStart + 1, preStart + leftSize,
                  inorder, inStart, index - 1);

root.right = build(preorder, preStart + leftSize + 1, preEnd,
                   inorder, index + 1, inEnd);

3.2 通过后序和中序数组构造二叉树

该题目和 3.1 框架类似，可以看下两种数组的特点


int leftSize = index - inStart;

root.left = build(inorder, inStart, index - 1,
                  postorder, postStart, postStart + leftSize - 1);

root.right = build(inorder, index + 1, inEnd,
                   postorder, postStart + leftSize, postEnd - 1);

3.3 通过后序和前序数组构造二叉树

这道题和前两道题有一个本质的区别：

通过前序中序，或者后序中序遍历结果可以确定唯一一棵原始二叉树，但是通过前序后序遍历结果无法确定唯一的原始二叉树。

方案：

1、首先把前序遍历结果的第一个元素或者后序遍历结果的最后一个元素确定为根节点的值。

2、然后把前序遍历结果的第二个元素作为左子树的根节点的值。

3、在后序遍历结果中寻找左子树根节点的值，从而确定了左子树的索引边界，进而确定右子树的索引边界，递归构造左右子树即可。


class Solution {
    // 存储 postorder 中值到索引的映射
    HashMap<Integer, Integer> valToIndex = new HashMap<>();

    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        for (int i = 0; i < postorder.length; i++) {
            valToIndex.put(postorder[i], i);
        }
        return build(preorder, 0, preorder.length - 1,
                    postorder, 0, postorder.length - 1);
    }

    // 定义：根据 preorder[preStart..preEnd] 和 postorder[postStart..postEnd]
    // 构建二叉树，并返回根节点。
    TreeNode build(int[] preorder, int preStart, int preEnd,
                   int[] postorder, int postStart, int postEnd) {
        if (preStart > preEnd) {
            return null;
        }
        if (preStart == preEnd) {
            return new TreeNode(preorder[preStart]);
        }

        // root 节点对应的值就是前序遍历数组的第一个元素
        int rootVal = preorder[preStart];
        // root.left 的值是前序遍历第二个元素
        // 通过前序和后序遍历构造二叉树的关键在于通过左子树的根节点
        // 确定 preorder 和 postorder 中左右子树的元素区间
        int leftRootVal = preorder[preStart + 1];
        // leftRootVal 在后序遍历数组中的索引
        int index = valToIndex.get(leftRootVal);
        // 左子树的元素个数
        int leftSize = index - postStart + 1;

        // 先构造出当前根节点
        TreeNode root = new TreeNode(rootVal);
        // 递归构造左右子树
        // 根据左子树的根节点索引和元素个数推导左右子树的索引边界
        root.left = build(preorder, preStart + 1, preStart + leftSize,
                postorder, postStart, index);
        root.right = build(preorder, preStart + leftSize + 1, preEnd,
                postorder, index + 1, postEnd - 1);

        return root;
    }
}

四序列化

当二叉树中节点的值不存在重复时：

如果你的序列化结果中不包含空指针的信息，且你只给出一种遍历顺序，那么你无法还原出唯一的一棵二叉树。

如果你的序列化结果中不包含空指针的信息，且你会给出两种遍历顺序，那么按照前文 东哥手把手带你刷二叉树（构造篇） 所说，分两种情况：

2.1. 如果你给出的是前序和中序，或者后序和中序，那么你可以还原出唯一的一棵二叉树。

2.2. 如果你给出前序和后序，那么你无法还原出唯一的一棵二叉树。

如果你的序列化结果中包含空指针的信息，且你只给出一种遍历顺序，也要分两种情况：

3.1. 如果你给出的是前序或者后序，那么你可以还原出唯一的一棵二叉树。

3.2. 如果你给出的是中序，那么你无法还原出唯一的一棵二叉树。

力扣第 297 题「二叉树的序列化与反序列化open in new window」就是给你输入一棵二叉树的根节点 root，要求你实现如下一个类：


public class Codec {

    // 把一棵二叉树序列化成字符串
    public String serialize(TreeNode root) {}

    // 把字符串反序列化成二叉树
    public TreeNode deserialize(String data) {}
}

4.1 前序遍历



    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serialize(root, sb);
        return sb.toString();
    }

    // 前序遍历序列化
    private void serialize(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append("null").append(",");
            return;
        }

        // 前序遍历
        sb.append(root.val).append(",");
        serialize(root.left, sb);
        serialize(root.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        LinkedList<String> nodes = new LinkedList<>();
        for (String node : data.split(",")) {
            nodes.addLast(node);
        }
        return deserialize(nodes);
    }

    private TreeNode deserialize(LinkedList<String> nodes) {
        if (nodes.isEmpty()) {
            return null;
        }

         /******前序遍历位置******/
        // 列表最左侧就是根节点
        String rootVal = nodes.removeFirst();
        if (rootVal.equals("null")) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(rootVal));

        root.left = deserialize(nodes);
        root.right = deserialize(nodes);

        return root;
    }

4.2 后续遍历

后续遍历在序列化时基本相同，注意后序的位置。

在反序列化时，一定要注意一点，即要先遍历右子树，再遍历左子树。


    private TreeNode deserialize(LinkedList<String> nodes) {
        if (nodes.isEmpty()) {
            return null;
        }

        // 后续、从后向前取元素
        String rootVal = nodes.removeLast();
        if (rootVal.equals("null")) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(rootVal));

			  root.right = deserialize(nodes);
        root.left = deserialize(nodes);

        return root;
    }

五归并排序实质为后序递归

归并排序的代码如下：


MergeSort(array, left, right):
    if left < right:
        middle = (left + right) / 2
        MergeSort(array, left, middle)  // 递归地对左半部分进行归并排序
        MergeSort(array, middle + 1, right)  // 递归地对右半部分进行归并排序
        Merge(array, left, middle, right)  // 合并左右两个有序子数组

Merge(array, left, middle, right):
    n1 = middle - left + 1
    n2 = right - middle
    
    // 创建临时数组来存储左右两个子数组的元素
    Let leftArray[1...n1+1] and rightArray[1...n2+1] be new arrays
    
    // 将左半部分的元素复制到左临时数组
    for i = 1 to n1:
        leftArray[i] = array[left + i - 1]
    
    // 将右半部分的元素复制到右临时数组
    for j = 1 to n2:
        rightArray[j] = array[middle + j]
    
    leftArray[n1 + 1] = infinity  // 设置哨兵值，表示左临时数组的末尾
    rightArray[n2 + 1] = infinity  // 设置哨兵值，表示右临时数组的末尾
    
    i = 1
    j = 1
    
    // 逐个比较左右两个临时数组的元素，将较小的元素放回原始数组中
    for k = left to right:
        if leftArray[i] <= rightArray[j]:
            array[k] = leftArray[i]
            i = i + 1
        else:
            array[k] = rightArray[j]
            j = j + 1

关注MergeSort 方法，和后续递归相同。

所有的递归算法，本质都是在遍历一颗（递归）树，然后在节点（前中后序位置）上执行代码。写递归算法，本质是告诉该节点要做什么。