算法奇趣阁——递归中二叉树的精妙裁剪

文章标题：

算法妙趣屋——递归下二叉树的精巧剪裁

1.前言

二叉树里的深度搜索（展开阐述）

深度优先遍历（DFS，即DepthFirstTraversal）
，是我们在树或者图这类数据结构中常用的一种遍历手段。该算法会尽可能深入地搜索树或者图的分支，直至一条路径上的所有节点都被遍历完毕，之后回溯到上一层，再去探寻另一条路径进行遍历。
在二叉树中，常见的深度优先遍历有：前序遍历、中序遍历以及后序遍历。
由于树本身的定义就是递归式的，所以运用递归的方法来实现树的三种遍历不仅易于理解，而且代码十分简洁。并且前中后序三种遍历的唯一差别就在于访问根节点的时机不一样，在解题的时候，选取合适的遍历顺序，对算法的理解很有帮助。

1.计算布尔二叉树的值（medium）

题目链接：计算布尔二叉树的值
题目阐释：

给你一棵完整的二叉树的根节点，这棵树有这样的特征：
叶子节点的值要么是0要么是1，其中0代表False，1代表True。
非叶子节点的值要么是2要么是3，其中2代表逻辑或OR，3代表逻辑与AND。
计算一个节点值的方式如下：
要是节点是叶子节点，那么节点的值就是它自身，也就是True或者False。
不然的话，计算两个子节点的节点值，然后用该节点的运算符对两个子节点值进行运算。
返回根节点root经过布尔运算后的结果。
完整二叉树指的是每个节点有0个或者2个子节点的二叉树。
叶子节点是没有子节点的节点。

算法思路：

• 1. 针对规模为n的问题，需要算出当前节点的值。
• 1. 当节点值不是0或1时，规模为n的问题能够分解为规模为n-1的子问题：
• a：所有子节点的值；
• b：通过子节点的值运算得到当前节点值。
• 1. 当问题的规模变为n=1时，也就是叶子节点的值为0或1，我们可以直接获取当前节点值为0或1。

递归函数流程：

• 1. 当前问题规模为n=1时，即叶子节点，直接返回当前节点值
• 1. 递归求出左右子节点的值；
• 1. 通过判断当前节点的逻辑运算符，计算左右子节点值运算得到的结果；

class Solution {
public:
    bool evaluateTree(TreeNode* root) {
        if(root->left==nullptr||root->right==nullptr)
        {
            return root->val;
        }
        else
        {
          if(root->val==2)
          return evaluateTree(root->left)||evaluateTree(root->right);
          else
          return evaluateTree(root->left)&&evaluateTree(root->right);
        }
    }
};

2. 求根节点到叶节点数字之和（medium）

题目链接：求根节点到叶节点数字之和
题目说明：
给你一个二叉树的根节点root，树中每个节点都存着一个0到9之间的数字。
每一条从根节点到叶子节点的路径都代表一个数字：
比如，从根节点到叶子节点的路径1->2->3就表示数字123。
计算从根节点到叶子节点生成的所有数字的总和。
叶子节点是指没有子节点的节点。

解题思路：

解法（dfs-前序遍历） ：

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

在前序遍历的过程中，我们可以 向左右子树传递信息，并且在回溯时获取左右子树的返回值。递归函数能帮我们做两件事：

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

递归函数流程：

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

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

    int sumNumber(TreeNode* root,int x) {
        if(root==nullptr)
            return x;
        else
        {
            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;

    }
};

3.⼆叉树剪枝（medium）

题⽬链接：二叉树剪枝

题目讲解：

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

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

后序遍历的主要步骤：

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

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

    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 1;
        }
        else
            return false;
    }
};

4. ⼆叉搜索树中第k⼩的元素（medium）

题目描述：
给定一个二叉搜索树的根节点 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;
    }

    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);
        }
    }
};

好啦，关于递归的内容就讲解到这里啦，下一次会讲解搜索、回溯还有全排列的相关知识，咱们下次再见