计算好节点的数量

Question

问题陈述

我无法理解我的代码出了什么问题，也很难理解下面的约束。

我的伪代码：

1. 遍历树级别顺序并构造数组表示（输入实际上作为单个根给出，但它们使用数组表示来显示完整的树）
2. 循环访问此数组表示形式，跳过空节点
3. 对于每个节点，让我们称之为X，向上迭代，直到我们到达根检查，看看是否在路径中的任何一点，parentNode

限制条件：

• 二叉树中的节点数在[1,10^5]范围内。
• 每个节点的值在[-10^4,10^4]之间

首先：我对约束的困惑是，自动测试会给出输入，如＜code＞2,4,4，null，1,3，null，null，5，null，null，null，null，5,4，4〕

其次：对于上面的输入，我的代码输出8，期望值是6，但是当我从数组中绘制树时，我也认为答案应该是8！

输入树

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        
        
        arrRepresentation = []
        
        queue = []
        
        queue.append(root)
        
        # while queue not empty
        while queue:
            # remove node
            node = queue.pop(0)
            if node is None:
                arrRepresentation.append(None)
                
            else:
                arrRepresentation.append(node.val)

            
          
            if node is not None:
                # add left to queue
                queue.append(node.left)

                # add right to queue
                queue.append(node.right)
            
        
        print(arrRepresentation)
        goodNodeCounter = 1

                
        # iterate over array representation of binary tree
        for k in range(len(arrRepresentation)-1, 0, -1):
            child = arrRepresentation[k]
            if child is None:
                continue
            isGoodNode = self._isGoodNode(k, arrRepresentation)
            print('is good: ' + str(isGoodNode))

            if isGoodNode:
                goodNodeCounter += 1
                
           
                
            
        
        return goodNodeCounter

        
    def _isGoodNode(self, k, arrRepresentation):
        
        child = arrRepresentation[k]
        print('child: '+str(child))
        # calculate index of parent
        parentIndex = (k-1)//2
        
        isGood = True
        # if we have not reached root node
        while parentIndex >= 0:
            parent = arrRepresentation[parentIndex]
            print('parent: '+ str(parent))
            # calculate index of parent
            parentIndex = (parentIndex-1)//2
            
            if parent is None:
                continue
            
            if parent > child:
                isGood = False
                break
                
           
                
        return isGood
        
        
        




Answer 1

您提供的二进制堆对应于后续层次结构：

tree = [2,4,4,4,None,1,3,None,None,5,None,None,None,None,5,4,4]
printHeapTree(tree)

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

在该树中，只有项值＜code＞1

请注意，列表中有一些值是不可访问的，因为它们的父级为null（无），因此它们不是树的一部分（但这可能是复制/粘贴错误）。如果我们用其他东西替换这些无值以使它们成为树的一部分，我们可以看到不可访问节点在层次结构中的位置：

t = [2,4,4,4,'*', 1,3,'*',None, 5,None, None,None,None,5,4,4]
printHeapTree(t)

          2
       __/ \_
      4      4
     / \    / \
    4   *  1   3
   /   /        \
  *   5          5
 / \
4   4

这可能是结果8（不将根视为好）与结果6（将根视为好）之间的差异的来源。

您可以在此处找到printHeapTree（）函数。

Answer 2

既然你想用广度优先搜索来解决：

from collections import deque

class Solution:
    def goodNodes(self,root:TreeNode)->int:
        if not root:
            return 0        
        queue=deque()
        # run bfs  with track of max_val till its parent node
        queue.append((root,-inf))
        res=0
        while queue:
            current,max_val=queue.popleft()
            if current.val>=max_val:
                res+=1
            if current.left:   
                queue.append((current.left,max(max_val,current.val)))
            
            if current.right:
                queue.append((current.right,max(max_val,current.val)))           
        return res

我将节点及其max_value添加到它的父节点。我不能添加全局max_value，因为看看这棵树：

对于前3个节点，您将拥有这个[3,1,4]，如果您在全局范围内保持max_val，max_val将是4。

下一个节点是3，左边的叶子节点。因为max_node是4，3

Answer 3

递归可能更容易：

class Node:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def good_nodes(root, maximum=float('-inf')):
    if not root: # null-root
        return 0

    is_this_good = maximum <= root.val # is this root a good node?

    maximum = max(maximum, root.val) # update max
    good_from_left = good_nodes(root.left, maximum) if root.left else 0
    good_from_right = good_nodes(root.right, maximum) if root.right else 0

    return is_this_good + good_from_left + good_from_right

tree = Node(2, Node(4, Node(4)), Node(4, Node(1, Node(5, None, Node(5, Node(4), Node(4)))), Node(3)))
print(good_nodes(tree)) # 6

基本上，递归遍历树，同时更新到目前为止看到的最大数量。在每次迭代中，将根的值与最大值进行比较，并在必要时递增计数器。