在二叉树Leetcode解决方案中计算好节点


难度级别 中等
经常问 亚马逊 微软
二叉树 深度优先搜索

问题陈述

在这个问题上 二叉树 被赋予根源。 如果在从根到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)。