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.
notion image
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; };