在二叉樹Leetcode解決方案中計算良好節點


難度級別
經常問 亞馬遜 Microsoft微軟
二叉樹 深度優先搜索

問題陳述

在這個問題上 二叉樹 被賦予根源。 如果在從根到X的路徑中沒有值大於X的節點,則樹中的節點X命名為好。

我們必須返回給定二叉樹中好的節點的數量。

    3
   / \
  1   4
 /   / \
3   1   5
4

說明:

在二叉樹Leetcode解決方案中計算良好節點

藍色的節點很好。
根節點(3)始終是一個好的節點。
節點4->(3,4)是從根開始的路徑中的最大值。
節點5->(3,4,5)是路徑中的最大值
節點3->(3,1,3)是路徑中的最大值。

    3
   /
  3
 / \
4   2
3

說明:

在二叉樹Leetcode解決方案中計算良好節點

節點2->(3、3、2)不好,因為“ 3”高於它。

途徑

為了確定一個節點是否良好,我們必須遍歷從根到該節點的路徑,並檢查其值是否不小於該路徑中的最大值。
為了找到好節點的數量,我們必須像這樣檢查給定二叉樹的每個節點。 但是在這裡觀察一件事,

如果我們通過遍歷某個特定節點從根到路徑的路徑找到答案,那麼我們也可以從那裡本身轉到其子節點,因為我們也已經遍歷了幾乎所有子節點的路徑,並且到目前為止還遍歷了最大值。 我們只需要用當前節點值更新最大值即可轉移到其兩個子節點。
因此,這看起來像DFS或遞歸,我們要遍歷從根到該節點的路徑,然後再轉到特定節點。 因此,在此問題中遞歸將非常有幫助。 這些步驟是:

  • 創建一個以兩個參數為參數的遞歸函數。 一個是節點的地址,第二個是我們找到的最大值。
  • 現在,無論何時我們到達特定節點,我們都將檢查當前節點值是否小於當前最大值。 如果不小於此值,則將這個節點添加到ans中,並在更新最大值後對其子節點調用相同的函數。

履行

用於在二叉樹Leetcode解決方案中計算良好節點的C ++程序

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left,*right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int rec(TreeNode* root, int mx)
{
   if(!root) return 0;

    int cur=0;
    if(mx <= root->val) cur++;

    mx=max(mx,root->val);
    return rec(root->left,mx) + rec(root->right,mx) + cur;
}

int goodNodes(TreeNode* root) {

    int mx= INT_MIN;
    return rec(root,mx);
}

int main() 
{
    TreeNode* root= new TreeNode(3);
    root->left=  new TreeNode(1);
    root->right=  new TreeNode(4);
    root->left->left=  new TreeNode(3);
    root->right->left=  new TreeNode(1);
    root->right->right=  new TreeNode(5);
    
    cout<< goodNodes(root) ;
    return 0; 
}
4

二叉樹Leetcode解決方案中用於計數良好節點的Java程序

class Rextester{
    
static class TreeNode {
    int val;
    TreeNode left,right;
    TreeNode(int x)  {
        val=x;
        left=null;
        right=null;
    }
}
    
    static int rec(TreeNode root, int mx)
    {
        if(root==null) return 0;
        
        int cur=0;
        if(mx <= root.val) cur++;
        
        mx = Math.max(mx,root.val);
        return rec(root.left,mx) + rec(root.right,mx) + cur;
    }
    
    public static int goodNodes(TreeNode root) 
    {     
        int mx= Integer.MIN_VALUE;
        return rec(root,mx);       
    }
    
  public static void main(String args[])
    {
        TreeNode root= new TreeNode(3);
        root.left=  new TreeNode(1);
        root.right=  new TreeNode(4);
        root.left.left=  new TreeNode(3);
        root.right.left=  new TreeNode(1);
        root.right.right=  new TreeNode(5);
        
        System.out.println( goodNodes(root) );
    }
}
4

二叉樹Leetcode解決方案中計數良好節點的複雜性分析

時間複雜度

上) : 其中n是給定二叉樹中節點的總數。 我們訪問每個節點一次。

空間複雜度 

上) : 使用的空間將是遞歸堆棧的最大大小。 在最壞的情況下,如果二叉樹傾斜,它的大小可以達到O(n)。