[算法] 第二集 二叉树中的深度搜索

深度优先遍历（DFS，全称为 Depth First Traversal），是我们树或者图如许的数据布局中常⽤的     ⼀种遍历算法。这个算法会尽可能深的搜索树或者图的分支，直到⼀条路径上的全部节点都被遍历     完毕，然后再回溯到上⼀层，继续找⼀条路遍历。     在⼆叉树中，常见的深度优先遍历为：前序遍历、中序遍历以及后序遍历。     因为树的界说本⾝就是递归界说，因此采⽤递归的方法去实现树的三种遍历不但容易明白⽽且代码很简洁。并且前中后序三种遍历的唯⼀区别就是访问根节点的机遇差异，在做题的时候，选择⼀个得当的遍历次序，对于算法的明白是非常有帮助的。   一、盘算布尔二叉树的值

1.题目形貌

2.算法思路

书面表明就是：
      1. 对于规模为 n 的问题，需要求恰当前节点值。          2. 节点值不为 0 或 1 时，规模为 n 的问题可以被拆分为规模为 n-1 的子问题：        a. 全部子节点的值；        b. 通过子节点的值运算出当前节点值。          3. 当问题的规模变为 n=1 时，即叶⼦节点的值为 0 或 1，我们可以直接获取当前节点值为 0 或 1。      绘图来明白一下：   

    我们如果想知道根节点true or false，我们需要知道其子节点，true or false，进而层层递归   

  3.代码实现

1. class Solution
2. {
3. public:
4.     bool evaluateTree(TreeNode* root)
5.     {
6.         if(root->left == nullptr)
7.         {
8.             return root->val == 0 ? false : true;
9.         }
10.         bool left = evaluateTree(root->left);
11.         bool right = evaluateTree(root->right);
12.         return root->val == 2 ? left | right : left & right;
13.     }
14. };

复制代码

二、求根节点到叶节点数字之和

1.题目形貌

2.算法思路

          通过前序遍历，往左右子树转达信息，并且在回溯时得到左右子树的返回值。让递归函数完成两件事：           1. 将父节点的数字与当前节点的信息整合到⼀起，盘算出当前节点的数字，然后转达到下⼀层举行递归；           2. 当遇到叶子节点的时候，就不再向下转达信息，将整合的结果向上⼀直回溯到根节点。           在递归竣事时，根节点需要返回的值也就被更新为了整棵树的数字和。                   递归函数计划：int dfs(TreeNode* root, int num)              1. 返回值：当前子树盘算的结果（数字和）；              2. 参数 num：递归过程中往下转达的信息（父节点的数字）；              3. 函数作用：整合父节点的信息与当前节点的信息盘算当前节点数字，并向下转达，再回溯时返回当前子树（当前节点作为子树根节点）数字和。              我们绘图来明白一下,举个例子:          我们有如下二叉树   

          首先,我们    合父节点的信息与当前节点的信息盘算当前节点数字，并向下转达:   

          溯时返回当前子树（当前节点作为子树根节点）数字和:   

          最后返回盘算的和就行了                         递归函数流程：              1. 当遇到空节点的时候，说明这条路从根节点开始没有分⽀，返回 0；              2. 结合⽗节点传下的信息以及当前节点的 val，盘算出当前节点数字 sum；              3. 如果当前结点是叶子节点，直接返回整合后的结果 sum；              4. 如果当前结点不是叶父节点，将 sum 传到左右子树中去，得到左右子树中节点路径的数字和，然 后相加后返回结果。             3.代码实现

   

1. class Solution {
2. public:
3.     int dfs(TreeNode* root, int prevSum)
4.     {
5.         if (root == nullptr)
6.         {
7.             return 0;
8.         }
9.         int sum = prevSum * 10 + root->val;
10.         if (root->left == nullptr && root->right == nullptr)
11.         {
12.             return sum;
13.         } else
14.         {
15.             return dfs(root->left, sum) + dfs(root->right, sum);
16.         }
17.     }
18.     int sumNumbers(TreeNode* root) {
19.         return dfs(root, 0);
20.     }
21. };

复制代码

  
   三、二叉树剪枝

    1.题目形貌

2.算法思路

   如果我们选择从上往下删除，我们需要收集左右⼦树的信息，这可能导致代码编写相对困难。然而， 通过观察我们可以发现，如果我们先删除最底部的叶子节点，然后再处理删除后的节点，最终的结果并不会受到影响。 因此，我们可以采⽤后序遍历的方式来办理这个问题。在后序遍历中，我们先处理左子树，然后处理 右子树，最后再处理当前节点。在处理当前节点时，我们可以判定其是否为叶子节点且其值是否为 0，     如果满足条件，我们可以删除当前节点。        • 需要注意的是，在删除叶子节点时，其父节点很可能会成为新的叶子节点。因此，在处理完子节点后，我们仍旧需要处理当前节点。这也是为什么选择后序遍历的原因（后序遍历⾸先遍历到的肯定是叶子节点）。        • 通过使用后序遍历，我们可以渐渐删除叶子节点，并且包管删除后的节点仍旧满足删除操作的要        求。如许，我们可以较为方便地实现删除操作，而不会影响最终的结果。        • 若在处   理竣事后全部叶子节点的值均为 1，则全部子树均包含 1，此时可以返回。         算法流程：            递归函数计划：void dfs(TreeNode*& root)           1. 返回值：无；           2. 参数 ：当前需要处理的节点；           3. 函数作用：判定当前节点是否需要删除，若需要删除，则删除当前节点。           后序遍历的主要流程：                1. 递归出口：当传入节点为空时，不做任何处理；              2. 递归处理左子树；              3. 递归处理右子树；              4. 处理当前节点：判定该节点是否为叶⼦节点（即左右⼦节点均被删除，当前节点成为叶子节点），              并且节点的值为 0：              a. 如果是，就删撤除；              b. 如果不是，就不做任何处理。          3.代码实现:

      

1. class Solution
2. {
3. public:
4. TreeNode* pruneTree(TreeNode* root)
5. {
6. if(root == nullptr) return nullptr;
7. root->left = pruneTree(root->left);
8. root->right = pruneTree(root->right);
9. if(root->left == nullptr && root->right == nullptr && root->val == 0)
10. {
11. delete root; // 防⽌内泄漏
12. root = nullptr;
13. }
14. return root;
15. }
16. };

复制代码

   
       四、验证二叉搜索树

  1.题目形貌

  

  2.算法思路

     如果一棵树是二叉搜索树，那么它的中序遍历的结果肯定是⼀个严酷递增的序列。 因此，我们可以初始化⼀个无穷小的全区变量，用来记载中序遍历过程中的前驱结点。那么就可以在中序遍历的过程中，先判定是否和前驱结点构成递增序列，然后修改前驱结点为当前结点，传入下一层的递归中。        算法流程：        

•  初始化⼀个全局的变量 prev，⽤来记载中序遍历过程中的前驱结点的 val；
  
•  中序遍历的递归函数中：           a. 设置递归出⼝：root == nullptr 的时候，返回 true；                 b. 先递归判定左⼦树是否是⼆叉搜索树，⽤ retleft 标记；                 c. 然后判定当前结点是否满⾜⼆叉搜索树的性子，用 retcur 标记：                 ▪ 如果当前结点的 val ⼤于 prev，说明满足条件，retcur 改为 true；                 ▪ 如果当前结点的 val ⼩于即是 prev，说明不满⾜条件，retcur 改为 false；                 d. 最后递归判定右⼦树是否是⼆叉搜索树，⽤ retright 标记；
  
• 只有当 retleft、 retcur 和 retright 都是 true 的时候，才返回 true。
  

    3.代码实现

  

1. class Solution
2. {
3. public:
4.      long prev = LONG_MIN;
5.      bool isValidBST(TreeNode* root)
6. {
7.      if(root == nullptr) return true;
8.      bool left = isValidBST(root->left);
9.      // 剪枝
10.      if(left == false) return false;
11.      bool cur = false;
12.      if(root->val > prev)
13.      cur = true;
14.      // 剪枝
15.      if(cur == false) return false;
16.      prev = root->val;
17.      bool right = isValidBST(root->right);
18.      return left && right && cur;
19. }
20. };
22. ​

复制代码

---

  感谢大家的观看，如有错误接待指正！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。