นับโหนดที่ดีใน Binary Tree ใน C++

สมมติว่าเรามี binary tree โหนด X ถือว่า "ดี" (good) ถ้าในเส้นทางจาก root ถึง X ไม่มีโหนดไหนมีค่ามากกว่า X เราต้องนับจำนวนโหนดที่ดี

ตัวอย่าง: ต้นไม้ [3,1,4,3,null,1,5] ผลลัพธ์ = 4

วิธีแก้ปัญหา (DFS)

DFS พร้อมส่งค่าสูงสุดที่เจอมาใน path (max_so_far)
ที่แต่ละโหนด: ถ้า node->val >= max_so_far นับ +1
เรียกซ้ำ left/right พร้อม max(max_so_far, node->val)
เริ่มต้น max_so_far = INT_MIN

ตัวอย่างโค้ด 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; 
    } 
}; 

void insert(TreeNode **root, int val){ 
    queue<TreeNode*> q; 
    q.push(*root); 
    while(q.size()){ 
        TreeNode *temp = q.front(); q.pop(); 
        if(!temp->left){ 
            if(val != NULL) temp->left = new TreeNode(val); 
            else temp->left = new TreeNode(0); 
            return; 
        } else q.push(temp->left); 
        if(!temp->right){ 
            if(val != NULL) temp->right = new TreeNode(val); 
            else temp->right = new TreeNode(0); 
            return; 
        } else q.push(temp->right); 
    } 
} 

TreeNode *make_tree(vector<int> v){ 
    TreeNode *root = new TreeNode(v[0]); 
    for(int i = 1; i<v.size(); i++) insert(&root, v[i]); 
    return root; 
} 

class Solution { 
public: 
    int ret; 
    void dfs(TreeNode* node, int val){ 
        if (!node) return; 
        ret += val <= node->val; 
        dfs(node->left, max(val, node->val)); 
        dfs(node->right, max(val, node->val)); 
    } 
    int goodNodes(TreeNode* root){ 
        ret = 0; 
        dfs(root, INT_MIN); 
        return ret; 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<int> v = {3,1,4,3,NULL,1,5}; 
    TreeNode *root = make_tree(v); 
    cout << (ob.goodNodes(root)); 
}

ข้อมูลนำเข้า

{3,1,4,3,NULL,1,5}