二叉树好节点计数代码输出不符及约束理解问题咨询

我无法定位代码的错误点，同时对下述题目约束存在疑问：

伪代码思路 #

1. 对二叉树做层序遍历，构造数组表示形式（输入实际为单个根节点，平台用数组形式展示完整树结构）
2. 遍历该数组，跳过取值为null的节点
3. 对每个节点X，向上遍历直到根节点，检查路径上是否存在parentNode > nodeX的情况，若存在则X不是好节点
4. 若节点为好节点则计数器加1

题目约束 #

• 二叉树的节点数范围为[1, 10^5]
• 每个节点的取值范围为[-10^4, 10^4]

疑问1 #

我对约束的困惑是，自动化测试给出的输入如[2,4,4,4,null,1,3,null,null,5,null,null,null,null,5,4,4]，如果按照子节点下标为c1 = 2k+1、c2 = 2k+2，父节点下标为parent = (k-1)//2的规则，说明树中存在值为null的节点。

疑问2 #

针对上述输入，我的代码输出结果为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

核心错误点 #

1. 父子下标规则不适用：你使用的c1=2k+1、parent=(k-1)//2的下标规则，仅适用于没有null节点的完全二叉树数组。你通过层序遍历把所有null节点都塞进数组后，数组里的非null节点的下标已经不符合这个规则，计算出来的父节点根本不是实际树结构里的父节点，路径检查完全错误，这就是你得到8而预期是6的直接原因。
2. 时间复杂度不满足要求：题目节点上限是1e5，你每个节点都向上遍历到根，最坏时间复杂度是O(n²)，对于链式二叉树的场景会直接超时，无法通过大数据量测试用例。

正确解法思路 #

直接在遍历树的过程中记录当前路径的最大值即可：

• 用DFS或BFS遍历每个节点，遍历的时候携带当前路径从根到当前节点的最大值
• 若当前节点值≥路径最大值，该节点是好节点，计数器加1，同时更新路径最大值为当前节点值
• 递归/遍历左右子节点即可
  该方法时间复杂度O(n)，空间复杂度O(h)（h为树高度），完全符合题目约束。

内容的提问来源于stack exchange，提问作者MPC