Count Good Nodes in Binary Tree

Link

https://leetcode.com/problems/count-good-nodes-in-binary-tree/

Deadline

Sep 11, 2022

Status

Archived

Type

Binary Tree

DFS

BFS

Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.

Return the number of good nodes in the binary tree.

Constraints:

The number of nodes in the binary tree is in the range [1, 10^5].

Each node's value is between [-10^4, 10^4].

풀이

효성

깨달은 것 : 자식 노드의 max값은 return 되어 사라진다!


var goodNodes = function(root) {
    let answer = 0;
    
    const dfs = (node, max) => {
        if(!node) return;
        
        if(node.val >= max) answer += 1;
	      max = Math.max(node.val, max);
        
        node.right && dfs(node.right, max);
        node.left && dfs(node.left, max);
    }
    
    dfs(root, root.val);
    
    return answer;
};

재영


/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var goodNodes = function(root) {
    let cnt = 0;
    
    const dfs = (node, maxValue) => {
        if (!node) return;
        
        const currMaxValue = Math.max(maxValue, node.val); 
        if (node.val === currMaxValue) cnt += 1;
        
        if (node.left) dfs(node.left, currMaxValue)
        if (node.right) dfs(node.right, currMaxValue)
    }
    
    dfs(root, -10001);
    
    return cnt;
};