{"id":6785,"date":"2020-05-17T19:12:45","date_gmt":"2020-05-18T02:12:45","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6785"},"modified":"2020-05-17T19:13:25","modified_gmt":"2020-05-18T02:13:25","slug":"leetcode-1448-count-good-nodes-in-binary-tree","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-1448-count-good-nodes-in-binary-tree\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1448. Count Good Nodes in Binary Tree"},"content":{"rendered":"\n

Given a binary tree root<\/code>, a node X<\/em> in the tree is named good<\/strong> if in the path from root to X<\/em> there are no nodes with a value greater than<\/em> X.<\/p>\n\n\n\n

Return the number of good<\/strong> nodes in the binary tree.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> root = [3,1,4,3,null,1,5]\nOutput:<\/strong> 4\nExplanation:<\/strong> Nodes in blue are good<\/strong>.\nRoot Node (3) is always a good node.\nNode 4 -> (3,4) is the maximum value in the path starting from the root.\nNode 5 -> (3,4,5) is the maximum value in the path\nNode 3 -> (3,1,3) is the maximum value in the path.<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> root = [3,3,null,4,2]\nOutput:<\/strong> 3\nExplanation:<\/strong> Node 2 -> (3, 3, 2) is not good, because \"3\" is higher than it.<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> root = [1]\nOutput:<\/strong> 1\nExplanation:<\/strong> Root is considered as good<\/strong>.<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • The number of nodes in the binary tree is in the range [1, 10^5]<\/code>.<\/li>
  • Each node’s value is between [-10^4, 10^4]<\/code>.<\/li><\/ul>\n\n\n\n
    Solution: Recursion<\/strong><\/h2>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \/\/ Author: Huahua\nclass Solution {\npublic:\n  int goodNodes(TreeNode* root, int max_val = INT_MIN) {\n    if (!root) return 0;    \n    return goodNodes(root->left, max(max_val, root->val))\n           + goodNodes(root->right, max(max_val, root->val))\n           + (root->val >= max_val ? 1 : 0);\n  }\n};<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[45],"tags":[177,17,28],"class_list":["post-6785","post","type-post","status-publish","format-standard","hentry","category-tree","tag-medium","tag-recursion","tag-tree","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6785","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=6785"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6785\/revisions"}],"predecessor-version":[{"id":6787,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6785\/revisions\/6787"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6785"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6785"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6785"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}