算法题:如何实现求和树?

2021年3月21日17:00:56 发表评论 698 次浏览

给定二叉树。检查它是否是求和树

二叉树是一个求和树, 其中每个节点x的值等于其左子树和右子树中存在的节点之和。空树也是求和树, 因为可以将空树的和视为0。叶节点也被视为求和树。

范例1:

Input:
    3
  /   \    
 1     2

Output: 1
Explanation: The given tree is a sum 
tree so return a boolean true.

范例2:

Input:

          10
        /    \
      20      30
    /   \ 
   10    10

Output: 0
Explanation: The given tree is not a sum
tree. For the root node, sum of elements
in left subtree is 40 and sum of elements
in right subtree is 30. Root element = 10
which is not equal to 30+40.

你的任务:

你不需要读取输入或打印任何东西。完成函数isSumTree(),它接受根节点作为输入参数,如果树是SumTree则返回true,否则返回false。

预期时间复杂度:O(N)

预期辅助空间:O(树高)

限制条件:

1≤节点数≤10^4

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: