C++で二分木内の「子孫の値以上となるノード」を数える方法【DFS解説】

二分木の根 root が与えられたとき、「自分自身の値が、すべての子孫の値以上である」という条件を満たすノードの個数を求める問題です。

たとえば、次のような二分木が入力として与えられたとします。

この場合の出力は 4 になります。値が 3 のノード以外は、すべてこの条件を満たしているためです。

解き方のアプローチ

この問題は、深さ優先探索（DFS）を使うことで効率的に解けます。各ノードに対して「その部分木内の最大値」をボトムアップに返しながら、条件を満たすノードをカウントしていくのがポイントです。手順は以下のとおりです。

• dfs() 関数を定義します。引数としてノードを受け取ります。
• ノードが NULL の場合は 0 を返します。
• l := dfs(ノードの左の子) を計算します。
• r := dfs(ノードの右の子) を計算します。
• ノードの値が max(l, r) 以上であれば、カウンタ ret を 1 増やします。
• x := max(ノードの値, l, r) を計算し、x を返します。

メインの処理では、次のように行います。

• ret := 0 で初期化します。
• dfs(root) を呼び出します。
• ret を返します。

それでは、実際の実装を見て理解を深めましょう。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
class TreeNode {
   public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data) {
      val = data;
      left = NULL;
      right = NULL;
   }
};
class Solution {
   public:
   int ret;
   int dfs(TreeNode* node){
      if(!node)
         return 0;
      int l = dfs(node->left);
      int r = dfs(node->right);
      if(node->val >= max(l, r)) {
         ret++;
      }
      int x = max({node->val, l, r});
      return x;
   }
   int solve(TreeNode* root) {
      ret = 0;
      dfs(root);
      return ret;
   }
};
main(){
   Solution ob;
   TreeNode *root = new TreeNode(7);
   root->left = new TreeNode(4);
   root->right = new TreeNode(3);
   root->right->left = new TreeNode(7);
   root->right->right = new TreeNode(5);
   cout << (ob.solve(root));
}

入力

TreeNode *root = new TreeNode(7);
root->left = new TreeNode(4);
root->right = new TreeNode(3);
root->right->left = new TreeNode(7);
root->right->right = new TreeNode(5);

出力

4

計算量について

このアルゴリズムでは、各ノードを一度ずつしか訪問しないため、時間計算量は O(N)（N はノード数）です。また、再帰呼び出しの深さがスタックに積まれるため、空間計算量は木の高さに依存し、最悪の場合（線形に連なった木）で O(N) となります。