【LeetCode Cookbook（C++ 描述）】一刷二叉树之递归遍历（DFS）（下）

本系列文章仅是 GitHub 大神 @halfrost 的刷题笔记 《LeetCode Cookbook》的提纲以及示例、题集的 C++转化。原书请自行下载学习。
本篇文章涉及新手应该优先刷的几道经典二叉树递归遍历算法题。

后序位置的特殊之处

需要特别注意的是，前中后序位置的代码，能力依次增强。前序位置的代码只能从函数参数中获取父节点传递来的数据；中序位置的代码不仅可以获取参数数据，还可以获取到左子树通过函数返回值传递回来的数据；而后序位置的代码额外地还可以同时获取到左右子树通过函数返回值传递回来的数据。

所以，某些情况下把代码移到后序位置效率最高；有些事情，只有后序位置的代码能做。

我们可以借两个例子来直观感受一下二者能力的区别——首先，如果把根节点看做第 1 层，如何打印出每一个节点所在的层数？

void traverse(TreeNode* root, int level) {
    if (root == nullptr) return;
    //前序位置
    printf("节点 %s 在第 %d 层", root->val, level);
    traverse(root->left, level + 1);
    traverse(root->right, level + 1);
}

traverse(root, 1);

其次，如何打印出每个节点的左右子树各有多少节点？

//定义：输入一棵二叉树，返回这棵二叉树的节点总数
int count(TreeNode* root) {
    if (root == nullptr) return 0;

    int leftCount = count(root->left);
    int rightCount = count(root->right);
    //后序位置
    printf("节点 %p 的左子树有 %d 个节点，右子树有 %d 个节点", root, leftCount, rightCount);

    return leftCount + rightCount + 1;
}

这两个问题的根本区别在于，一个节点所在的层数，从根节点遍历过来的过程中就能顺便记录，用递归函数的参数就能传递下去；而以一个节点为根的整棵子树的节点数，必须遍历完子树之后通过递归函数的返回值拿到答案，因此只有后序位置才能通过返回值获取子树的信息。换言之，一旦题目和子树有关，则大概率要给函数设置合理的定义和返回值，在后序位置写代码。

给你一棵二叉树的根节点，返回该树的直径。

二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的长度由它们之间边数表示。

每一条二叉树的直径长度，就是一个节点的左右子树的最大深度之和。最为直接的思路是，我们遍历整棵树中的每个节点，然后通过每个节点的左右子树的最大深度（最大深度的求解我们在上篇文章就已经明确了）算出每个节点的直径，最后把所有直径求个最大值即可。

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

    int diameterOfBinaryTree(TreeNode* root) {
        //对每个节点计算直径，求最大直径
        traverse(root);
        return maxDiameter;
    }

private:
    // 遍历二叉树
    void traverse(TreeNode* root) {
        if (root == nullptr) return;
        //对每个节点计算直径
        int leftMax = maxDepth(root->left);
        int rightMax = maxDepth(root->right);
        int myDiameter = leftMax + rightMax;
        //更新全局最大直径
        maxDiameter = max(maxDiameter, myDiameter);

        traverse(root->left);
        traverse(root->right);
    }

    //计算二叉树的最大深度
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        
        int leftMax = maxDepth(root->left);
        int rightMax = maxDepth(root->right);
        return max(leftMax, rightMax) + 1;
    }
};

这一解法是正确的，但其时间复杂度为$O(n^2)$ ，运行时间较长，原因在于前序位置无法获取子树信息，只能让每个节点调用 maxDepth() 函数去算子树的深度，而 traverse() 遍历每个节点的时候还会调用递归函数 maxDepth() 从而遍历子树的所有节点。

我们进一步优化，把计算直径的逻辑放在后序位置——准确说应该是放在 maxDepth() 的后序位置，因为 maxDepth() 的后序位置是知道左右子树的最大深度的。

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

public:
    int diameterOfBinaryTree(TreeNode* root) {
        maxDepth(root);
        return maxDiameter;
    }
    
private:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;

        int leftMax = maxDepth(root->left);
        int rightMax = maxDepth(root->right);
        //后序位置，顺便计算最大直径
        int myDiameter = leftMax + rightMax;
        maxDiameter = max(maxDiameter, myDiameter);

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

优化后的算法时间复杂度降至$O(n)$ 。

⚠️ 利用后序位置的题目，一般都使用「分而治之」的思路。当前节点接收并利用了子树返回的信息，这就意味着你把原问题分解成了当前节点 + 左右子树的子问题。

LeetCode #654：Maximum Binary Tree 最大二叉树

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

1. 创建一个根节点，其值为 nums 中的最大值。
2. 递归地在最大值左边的子数组前缀上构建左子树。
3. 递归地在最大值右边的子数组后缀上构建右子树。

返回 nums 构建的最大二叉树。

每个二叉树节点都可以认为是一棵子树的根节点，我们要遍历数组，找到最大值 maxVal ，从而把根节点 root 构造出来，然后对 maxVal 左边的数组和右边的数组进行递归构建，作为 root 的左右子树。

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return build(nums, 0, nums.size() - 1);
    }

private:
    //定义：将 nums[lo..hi] 构造成符合条件的树，返回根节点
    TreeNode* build(vector<int>& nums, int lo, int hi) {
        // base case
        if (lo > hi) return nullptr;
        //找到数组中的最大值和对应的索引
        int index = -1, maxVal = INT_MIN;
        for (int i = lo; i <= hi; i++) {
            if (maxVal < nums[i]) {
                index = i;
                maxVal = nums[i];
            }
        }
        //先构造出根节点
        TreeNode* root = new TreeNode(maxVal);
        //递归调用构造左右子树
        root->left = build(nums, lo, index - 1);
        root->right = build(nums, index + 1, hi);
        
        return root;
    }
};

LeetCode #105：Construct Binary Tree from Preorder and Inorder Traversal 从前序与中序遍历序列构造二叉树

给定一棵树的前序遍历 preorder 与中序遍历 inorder 。请构造二叉树并返回其根节点。

题中给出数组是同一棵树不同遍历方式所生成的不同结果。二叉树需要两种遍历结果来确定其完整结构，单一的遍历方式无法唯一地确定一棵二叉树的所有节点和它们之间的连接关系。对于本题目，从根、左子树，到右子树的前序遍历可以直接确定根节点，但无法确定左右子树的相对关系；而从左子树、根，到右子树的中序遍历则可以确定左右子树的相对位置。二者相结合，就可以推断出完整的目标二叉树结构。

与上一道题「最大二叉树」类似，我们要想办法确定根节点的值，把根节点找出来，然后递归构造左右子树即可。根据两种遍历顺序的差异，导致了数组 preoder 和 inorder 元素分布呈如下特点：

如图，前序遍历的第一个值 preorder[0] 即为根节点的值，两个数组分别有根节点左支与右支节点两个独立的部分，关键在于以何种方式通过根节点的值，将 preorder 和 inorder 数组划分成两半，构造根节点的左右子树。

仿照最大二叉树问题，我们依然初始化 build() 函数模块以构造二叉树：

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
	//根据函数定义，用 preorder 和 inorder 构造二叉树
    return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
}
//若前序遍历数组为 preorder[preStart..preEnd]，
//中序遍历数组为 inorder[inStart..inEnd]，
//构造二叉树，返回该二叉树的根节点
//函数签名
TreeNode* build(vector<int>& preorder, int preStart, int preEnd, vector<int>& inorder, int inStart, int inEnd);

前序遍历的根节点值 rootVal 很容易确定为 preStart = 0 ，而中序遍历的根节点 index 处于 inorder 数组之间某一位置。使用 for 循环确定 index 的效率并不高，因此我们考虑使用 unordered map（哈希表）存储元素到索引的映射，这一哈希表 valToIndex 定义在 build() 函数外部，buildTree() 直接遍历 inorder 将每个元素索引都映射到 valToIndex 。

//存储 inorder 中值到索引的映射
unordered_map<int, int> valToIndex;

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    for (int i = 0; i < inorder.size(); i++) valToIndex[inorder[i]] = i;

    return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
}

TreeNode* build(vector<int>& preorder, int preStart, int preEnd, 
                vector<int>& inorder, int inStart, int inEnd) {
    int rootVal = preorder[preStart];
    //避免 for 循环寻找 rootVal
    int index = valToIndex[rootVal];
    // ... 以下开始递归构建左右子树
}

在构建左右子树的时候，我们需要划定左右子树所对应数组的起始、终止索引，确保树结构的准确性，以正确地简化子问题，递归地构造出二叉树。

中序遍历数组 inorder 的左右子树范围较容易确定，左子树为 [inStart, index - 1] ，右子树则为 [index + 1, inEnd] ；而对于前序遍历数组 preorder ，左子树 root->left 的终止索引应为起始索引 preStart 与左子树长度 leftSize 之和，右子树 root->right 的起始索引显然就是左子树的终止索引 + 1 。这时候，我们可以发现，如果只选取一种遍历方式来推断二叉树，我们无法确切地知道左子树长度 leftSize 的大小；但是只要我们可以知道中序遍历的结果 index 的位置，我们就可以利用两种遍历方式所得左子树长度守恒推出恒等式 leftSize = index - inStart ，从而求解 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);

最后，我们再补充终止递归的基本条件 base case 即可完成问题所求。

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for (int i = 0; i < inorder.size(); i++) valToIndex[inorder[i]] = i;

        return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }

private:
	//存储 inorder 中值到索引的映射
    unordered_map<int, int> valToIndex;
    
    TreeNode* build(vector<int>& preorder, int preStart, int preEnd, 
                    vector<int>& inorder, int inStart, int inEnd) {

        if (preStart > preEnd) return NULL;   // base case
        // root 节点对应的值就是前序遍历数组的第一个元素
        int rootVal = preorder[preStart];
        // rootVal 在中序遍历数组中的索引
        int index = valToIndex[rootVal];
        
        int leftSize = index - inStart;
        //先构造出当前根节点
        TreeNode* root = new TreeNode(rootVal);
        //递归构造左右子树
        root->left = build(preorder, preStart + 1, preStart + leftSize, inorder, inStart, index - 1);
        root->right = build(preorder, preStart + leftSize + 1, preEnd, inorder, index + 1, inEnd);
        
        return root;
    }
};

该算法的时间复杂度为$O(n)$ ，维护一个哈希表，空间复杂度也为$O(n)$ 。

LeetCode #106：Construct Binary Tree from Inorder and Postorder Traversal 从中序与后序遍历序列构造二叉树

根据一棵树的中序遍历 inorder 与后序遍历 postorder 构造二叉树。

根据两种遍历方式的特点，可以归纳出 inorder 与 postorder 两个数组的元素分布：

构建辅助函数 build() ，函数签名如下：

TreeNode* build(vector<int>& inorder, int inStart, int inEnd, vector<int>& postorder, int postStart, int postEnd);

后序遍历的根节点值 rootVal 很容易确定为 postEnd = n - 1 ，而中序遍历的根节点 index 处于 inorder 数组之间某一位置。因此，中序遍历的左子树范围为 [inStart, index - 1] ，右子树的范围为[index + 1, inEnd] ；后序遍历的左子树范围为 [postStart, postStart + leftsize - 1] ，右子树的范围为 [postStart + leftSize, postEnd - 1] 。

class Solution {
public:
    
    
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        for (int i = 0; i < inorder.size(); i++) valToIndex[inorder[i]] = i;

        return build(inorder, 0, inorder.size() - 1,
                    postorder, 0, postorder.size() - 1);
    }
    
private:
	//存储 inorder 中值到索引的映射
    unordered_map<int, int> valToIndex;
    //构造二叉树，返回该二叉树的根节点 
    TreeNode* build(vector<int>& inorder, int inStart, int inEnd, vector<int>& postorder, int postStart, int postEnd) {
        if (inStart > inEnd) return nullptr;
        // root 节点对应的值就是后序遍历数组的最后一个元素
        int rootVal = postorder[postEnd];
        // rootVal 在中序遍历数组中的索引
        int index = valToIndex[rootVal];
        //左子树的节点个数
        int leftSize = index - inStart;
        TreeNode* root = new TreeNode(rootVal);
        //递归构造左右子树
        root->left = build(inorder, inStart, index - 1, postorder, postStart, postStart + leftSize - 1);
        root->right = build(inorder, index + 1, inEnd, postorder, postStart + leftSize, postEnd - 1);
        
        return root;
    }
};

LeetCode #889：Construct Binary Tree from Preorder and Postorder Traversal 从前序与后序遍历构造二叉树

给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有无重复值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。

如果存在多个答案，您可以返回其中任何一个。

通过前序中序，或者后序中序遍历结果可以确定唯一一棵原始二叉树，但是通过前序、后序遍历结果无法确定唯一的原始二叉树。对此，如题，我们只能返回任意一个可能解。大致思路如下：

1. 把前序遍历结果的第一个元素或者后序遍历结果的最后一个元素确定为根节点的值。
2. 把前序遍历结果的第二个元素作为左子树的根节点的值。
3. 在后序遍历结果中寻找左子树根节点的值，从而确定了左子树的索引边界，进而确定右子树的索引边界，递归构造左右子树。

class Solution {
public:
    TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
        for (int i = 0; i < postorder.size(); i++) {
            valToIndex[postorder[i]] = i;
        }
        return build(preorder, 0, preorder.size() - 1,
                    postorder, 0, postorder.size() - 1);
    }

private:
    //存储 postorder 中值到索引的映射
    unordered_map<int, int> valToIndex;
    //构建二叉树，并返回根节点。
    TreeNode* build(vector<int>& preorder, int preStart, int preEnd, vector<int>& postorder, int postStart, int postEnd) {
        if (preStart > preEnd) return nullptr;
        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[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;
    }
};

我们关注这一行代码：

int leftRootVal = preorder[preStart + 1];

我们假设前序遍历的第二个元素是左子树的根节点，然而实际上左子树有可能是空指针，那么这个元素就应该是右子树的根节点。由于这里无法确切进行判断，所以导致了最终答案的不唯一。