系列文章目录

算法----滑动窗口
算法----二叉树

文章目录

前言

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

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

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

（一）二叉树的遍历

1、递归遍历

二叉树递归遍历框架：

// 二叉树的遍历框架
void traverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    // 前序位置
    traverse(root->left);
    // 中序位置
    traverse(root->right);
    // 后序位置
}

只要这个先左后右的调用顺序不变：

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

那么 traverse 函数访问节点的顺序就是固定的。

之所以二叉树会有前/中/后序三种不同顺序的遍历结果，是因为我们在 traverse 函数中不同位置写代码，效果是不一样的。前中后序遍历的结果不同，原因是把代码写在了不同位置，所以产生了不同的效果。

前序位置的代码会在进入节点时立即执行；中序位置的代码会在左子树遍历完成后，遍历右子树之前执行；后序位置的代码会在左右子树遍历完成后执行。

♦特别强调♦
前中后序是遍历二叉树过程中处理每一个节点的三个特殊时间点，绝不仅仅是三个顺序不同的 List：

  • 前序位置的代码在刚刚进入一个二叉树节点的时候执行；
  • 后序位置的代码在将要离开一个二叉树节点的时候执行；
  • 中序位置的代码在一个二叉树节点左子树都遍历完，即将开始遍历右子树的时候执行。

2、层序遍历

层序遍历需要借助 队列 来实现，而且根据不同的需求，可以有三种不同的写法，下面一一列举。

写法一
这是最简单的写法，代码如下：

void levelOrderTraverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    std::queue<TreeNode*> q;
    q.push(root);	// 根节点入队
    while (!q.empty()) {
        TreeNode* cur = q.front();
        q.pop();
        // 访问 cur 节点
        std::cout << cur->val << std::endl;
        
        // 把 cur 的左右子节点加入队列
        if (cur->left != nullptr) {
            q.push(cur->left);
        }
        if (cur->right != nullptr) {
            q.push(cur->right);
        }
    }
}

写法二
对上面的解法稍加改造，就得出了下面这种写法：

void levelOrderTraverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    queue<TreeNode*> q;
    q.push(root);
    // 记录当前遍历到的层数（根节点视为第 1 层）
    int depth = 1;

    while (!q.empty()) {
        int sz = q.size();
        // 把一层的所有节点都操作完。pop自己 和 push子节点
        for (int i = 0; i < sz; i++) {
            TreeNode* cur = q.front();
            q.pop();
            // 访问 cur 节点，同时知道它所在的层数
            cout << "depth = " << depth << ", val = " << cur->val << endl;

            // 把 cur 的左右子节点加入队列
            if (cur->left) q.push(cur->left);
            if (cur->right) q.push(cur->right);
        }
        depth++;
    }
}

注意代码中的内层 for 循环：

int sz = q.size();
for (int i = 0; i < sz; i++) {
    ...
}

注意队列的长度 sz 一定要在循环开始前保存下来，因为在循环过程中队列的长度是会变化的，不能直接用 q.size() 作为循环条件。

这种写法就可以记录下来每个节点所在的层数，可以解决诸如二叉树最小深度这样的问题，是我们最常用的层序遍历写法。

写法三
回顾写法二，我们每向下遍历一层，就给 depth 加 1，可以理解为每条树枝的权重是 1，二叉树中每个节点的深度，其实就是从根节点到这个节点的路径权重和，且同一层的所有节点，路径权重和都是相同的。

那么假设，如果每条树枝的权重和可以是任意值，现在让你层序遍历整棵树，打印每个节点的路径权重和，你会怎么做？

这样的话，同一层节点的路径权重和就不一定相同了，写法二这样只维护一个 depth 变量就无法满足需求了。

写法三就是为了解决这个问题，在写法一的基础上添加一个 State 类，让每个节点自己负责维护自己的路径权重和，代码如下：

class State {
public:
    TreeNode* node;
    int depth;
    State(TreeNode* node, int depth) : node(node), depth(depth) {}
};

void levelOrderTraverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    queue<State> q;
    // 根节点的路径权重和是 1
    q.push(State(root, 1));

    while (!q.empty()) {
        State cur = q.front();
        q.pop();
        // 访问 cur 节点，同时知道它的路径权重和
        cout << "depth = " << cur.depth << ", val = " << cur.node->val << endl;

        // 把 cur 的左右子节点加入队列
        if (cur.node->left != nullptr) {
            q.push(State(cur.node->left, cur.depth + 1));
        }
        if (cur.node->right != nullptr) {
            q.push(State(cur.node->right, cur.depth + 1));
        }
    }
}

这样每个节点都有了自己的 depth 变量，是最灵活的，可以满足所有 BFS 算法的需求。但是由于要额外定义一个 State 类比较麻烦，所以非必要的话，用写法二就够了。

（二）二叉树心法 – 解题思路

二叉树题目的递归解法可以分两类思路，第一类是遍历一遍二叉树得出答案；第二类是通过分解问题计算出答案。

本节以二叉树的最大深度和前序遍历，来讨论这两种解题思路。

1、二叉树的最大深度

（1）遍历思维

遍历一遍二叉树，用一个外部变量记录每个节点所在的深度，取最大值就可以得到最大深度。

class Solution {
public:
    int depth = 0;
    int ans = 0;
    void traverse(TreeNode* root)
    {
        if(root == nullptr)
            return;
        depth ++;
        if(root->left == nullptr && root->right == nullptr)
            ans = max(depth, ans);
        traverse(root->left);
        traverse(root->right);
        depth --;
    }
    int maxDepth(TreeNode* root) {
        traverse(root);
        return ans;
    }
};

（2）分解问题思维

根据左右子树的最大深度推出原二叉树的最大深度。

class Solution {
public:
    int maxDepth(TreeNode* root) {
        int ans = 0;
        if(root == nullptr)
            return ans;
        int leftDepth = maxDepth(root->left);	// 左子树的最大深度
        int rightDepth = maxDepth(root->right);	// 右子树的最大深度
        return 1 + max(leftDepth, rightDepth);	// 最终结果
    }
};

2、二叉树的前序遍历

（1）遍历思路

// 用遍历的思路计算前序遍历结果
class Solution {
public:
    // 存放前序遍历结果
    vector<int> res;

    vector<int> preorderTraversal(TreeNode* root) {
        traverse(root);
        return res;
    }

    // 二叉树遍历函数
    void traverse(TreeNode* root) {
        if (root == nullptr) {
            return;
        }
        // 前序位置
        res.push_back(root->val);
        traverse(root->left);
        traverse(root->right);
    }
};

（2）分解问题思路

一棵二叉树的前序遍历结果 = 根节点 + 左子树的前序遍历结果 + 右子树的前序遍历结果。所以，这样实现前序遍历算法：

class Solution {
public:
    // 定义：输入一棵二叉树的根节点，返回这棵树的前序遍历结果
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }
        // 前序遍历的结果，root->val 在第一个
        res.push_back(root->val);
        // 利用函数定义，后面接着左子树的前序遍历结果
        vector<int> left = preorderTraversal(root->left);
        res.insert(res.end(), left.begin(), left.end());
        // 利用函数定义，最后接着右子树的前序遍历结果
        vector<int> right = preorderTraversal(root->right);
        res.insert(res.end(), right.begin(), right.end());
        return res;
    }
};

3、总结

综上，遇到一道二叉树的题目时的通用思考过程是：

  1. 是否可以通过遍历一遍二叉树得到答案？ 如果可以，用一个 traverse 函数配合外部变量来实现。

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

  3. 无论使用哪一种思维模式，你都要明白二叉树的每一个节点需要做什么，需要在什么时候（前中后序）做。

（三）二叉树心法 – 构造

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

三道题来熟悉套路：

  1. LeetCode 第 654 题「最大二叉树」
  2. LeetCode 第 105题「从前序和中序遍历序列构造二叉树」

第一题 最大二叉树

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

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

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

示例 1：
在这里插入图片描述

输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：

  • [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
    • [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
      • 空数组，无子节点。
      • [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
        • 空数组，无子节点。
        • 只有一个元素，所以子节点是一个值为 1 的节点。
    • [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
      • 只有一个元素，所以子节点是一个值为 0 的节点。
      • 空数组，无子节点。

遍历数组把找到最大值 maxVal，从而把根节点 root 做出来，然后对 maxVal 左边的数组和右边的数组进行递归构建，作为 root 的左右子树。

当前 nums 中的最大值就是根节点，然后根据索引递归调用左右数组构造左右子树即可。

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

    TreeNode* build(vector<int>& nums, int l, int r)
    {
        if(l > r) return nullptr;

        // 找到最大元素
        int index = 0, maxNum = INT_MIN;
        for(int i = l; i <= r; i++)
        {
            if(maxNum < nums[i])
            {
                maxNum = nums[i];
                index = i;
            }
        }
        TreeNode* node = new TreeNode(maxNum);

        node->left = build(nums, l, index-1);   // 构造左子树
        node->right = build(nums, index+1, r);  // 构造右子树

        return node;
    }
};

（四）后序位置的特殊之处

说后序位置之前，先简单说下前序和中序。

前序位置本身其实没有什么特别的性质，之所以你发现好像很多题都是在前序位置写代码，实际上是因为我们习惯把那些对前中后序位置不敏感的代码写在前序位置罢了。

中序位置主要用在 BST 场景中，你完全可以把 BST 的中序遍历认为是遍历有序数组。

★【重点】
仔细观察，前中后序位置的代码，能力依次增强。

  • 前序位置的代码只能从函数参数中获取父节点传递来的数据。

  • 中序位置的代码不仅可以获取参数数据，还可以获取到左子树通过函数返回值传递回来的数据。

  • 后序位置的代码最强，不仅可以获取参数数据，还可以同时获取到左右子树通过函数返回值传递回来的数据。

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

举些具体的例子来感受下它们的能力区别。现在给一棵二叉树，有两个简单的问题：

  1. 如果把根节点看做第 1 层，如何打印出每一个节点所在的层数？
  2. 如何打印出每个节点的左右子树各有多少节点？

第一个问题可以这样写代码：

// 二叉树遍历函数
void traverse(TreeNode root, int level) {
    if (root == null) {
        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 == null) {
        return 0;
    }
    int leftCount = count(root.left);
    int rightCount = count(root.right);
    // 后序位置
    printf("节点 %s 的左子树有 %d 个节点，右子树有 %d 个节点",
            root, leftCount, rightCount);

    return leftCount + rightCount + 1;
}

这两个问题的根本区别在于：一个节点在第几层，你从根节点遍历过来的过程就能顺带记录，用递归函数的参数就能传递下去；而以一个节点为根的整棵子树有多少个节点，你必须遍历完子树之后才能数清楚，然后通过递归函数的返回值拿到答案。

结合这两个简单的问题，你品味一下后序位置的特点，只有后序位置才能通过返回值获取子树的信息。

那么换句话说，一旦发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码了。

1、实例

以力扣第 543 题「二叉树的直径」，计算一棵二叉树的最长直径长度。
所谓二叉树的「直径」长度，就是任意两个结点之间的路径长度。最长「直径」并不一定要穿过根结点，比如下面这棵二叉树：
在这里插入图片描述
它的最长直径是 3，即 [4,2,1,3]，[4,2,1,9] 或者 [5,2,1,3] 这几条「直径」的长度。

解决这题的关键在于，每一条二叉树的「直径」长度，就是一个节点的左右子树的最大深度之和。

现在求整棵树中的最长「直径」，那直截了当的思路就是遍历整棵树中的每个节点，然后通过每个节点的左右子树的最大深度算出每个节点的「直径」，最后把所有「直径」求个最大值即可。

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

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

    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 1 + max(leftMax, rightMax);
    }
};
# 算法 # java # 数据结构
Logo
开源鸿蒙跨平台开发者社区

开源鸿蒙跨平台开发社区汇聚开发者与厂商，共建“一次开发，多端部署”的开源生态，致力于降低跨端开发门槛，推动万物智联创新。

更多推荐

cover

鸿蒙平台 Subversion 客户端适配实战：基于 HTTP_WebDAV 协议的轻量级 SVN 图形界面

avatar 开源鸿蒙跨平台开发者社区
cover

鸿蒙平台 InterModeller 概念建模工具适配实战：基于 Electron 壳方案的思维导图风格分类树开发

avatar 开源鸿蒙跨平台开发者社区
cover

电容触摸 GT911坐标定位校准—【万物智能之开源鸿蒙OpenHarmony系统实战开发系列教程】

avatar 开源鸿蒙跨平台开发者社区