二叉树递归遍历与剪枝算法详解

3. 求根节点到叶节点数字之和

题目链接：求根节点到叶节点数字之和

题目介绍

给你一个二叉树的根节点 root，树中每个节点都存放有一个 0 到 9 之间的数字。 每条从根节点到叶节点的路径都代表一个数字：例如，从根节点到叶节点的路径 1->2->3 表示数字 123。 计算从根节点到叶节点生成的所有数字之和。

解题思路

解法（DFS-前序遍历）：

前序遍历按照根节点、左子树、右子树的顺序遍历二叉树的所有节点，通常用于子节点的状态依赖于父节点状态的题目。

在前序遍历的过程中，我们可以往左右子树传递信息，并且在回溯时得到左右子树的返回值。递归函数可以帮我们完成两件事：

• 将父节点的数字与当前节点的信息整合到一起，计算出当前节点的数字，然后传递到下一层进行递归；
• 当遇到叶子节点的时候，就不再向下传递信息，而是将整合的结果向上一直回溯到根节点。在递归结束时，根节点需要返回的值也就被更新为了整棵树的数字和。

递归函数流程

1. 当遇到空节点的时候，说明这条路从根节点开始没有分支，返回 0。
2. 结合父节点传下的信息以及当前节点的 val，计算出当前节点数字 sum。
3. 如果当前结点是叶子节点，直接返回整合后的结果 sum。
4. 如果当前结点不是叶子节点，将 sum 传到左右子树中去，得到左右子树中节点路径的数字和，然后相加后返回结果。

代码示例

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        return sumNumber(root, 0);
    }

private:
    int sumNumber(TreeNode* root, int x) {
        if (root == nullptr) return x;
        x = x * 10 + root->val;
        if (root->left != nullptr && root->right != nullptr) return sumNumber(root->left, x) + sumNumber(root->right, x);
        else if (root->left != nullptr) return sumNumber(root->left, x);
        else if (root->right != nullptr) return sumNumber(root->right, x);
        else return x;
    }
};

4. 二叉树剪枝

题目链接：二叉树剪枝

题目介绍

给你二叉树的根结点 root，此外树的每个结点的值要么是 0，要么是 1。 返回移除了所有不包含 1 的子树的原二叉树。 节点 node 的子树为 node 本身加上所有 node 的后代。

解题思路

解法（DFS-后序遍历）：

后序遍历按照左子树、右子树、根节点的顺序遍历二叉树的所有节点，通常用于父节点的状态依赖于子节点状态的题目。

后序遍历的主要流程：

1. 递归出口：当传入节点为空时，不做任何处理。
2. 递归处理左子树。
3. 递归处理右子树。
4. 处理当前节点：判断该节点是否为叶子节点（即左右子节点均被删除，节点成为叶子节点），并且节点的值为 0：
   • 如果是，就删除掉；
   • 如果不是，就不做任何处理。

代码示例

class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        dfs(root);
        if (root->left == nullptr && root->right == nullptr && root->val == 0) return nullptr;
        else return root;
    }

private:
    bool dfs(TreeNode* root) {
        if (root) {
            if (root->left == nullptr && root->right == nullptr) return root->val;
            bool l = dfs(root->left);
            bool r = dfs(root->right);
            if (l == false) root->left = nullptr;
            if (r == false) root->right = nullptr;
            if (root->val == 0) return l || r;
            else return true;
        }
        return false;
    }
};

5. 二叉搜索树中第 k 小的元素

题目链接：二叉搜索树中第 k 小的元素

题目描述

给定一个二叉搜索树的根节点 root，和一个整数 k，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。

解题思路

（中序遍历 + 计数器剪枝）

上述解法不仅使用大量额外空间存储数据，并且会将所有的结点都遍历一遍。 但是，我们可以根据中序遍历的过程，只需扫描前 k 个结点即可。 因此，我们可以创建一个全局的计数器 count，将其初始化为 k，每遍历一个节点就将 count--。直到某次递归的时候，count 的值等于 0，说明此时的结点就是我们要找的结果。

代码示例

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        int flag = 0;
        dfs(root, k, flag);
        return flag;
    }

private:
    void dfs(TreeNode* root, int& k, int& flag) {
        if (root) {
            dfs(root->left, k, flag);
            k--;
            if (k == 0) flag = root->val;
            dfs(root->right, k, flag);
        }
    }
};