Teaching Kids Programming: Videos on Data Structures and Algorithms
Given a binary tree root, return whether for every node in the tree other than the leaves, its value is equal to the sum of its left child’s value and its right child’s value.
Constraints
n ≤ 100,000 where n is the number of nodes in root
Determine Sum Binary Tree via Breadth First Search Algorithm
Let’s perform a Depth First Search Algorithm to traverse the binary tree. At each node, we check if the value of the node (except when it is a leaf node) is equal to sum of its kid or children. Then we continuouly check the left and right subtree.
Time complexity is O(N) and space complexity is O(N) where N is the number of the nodes in the binary tree.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | # class Tree: # def __init__(self, val, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def solve(self, root): def dfs(root): if not root: return True x = 0 ans = True if root.left: ans = ans and dfs(root.left) x += root.left.val if root.right: ans = ans and dfs(root.right) x += root.right.val if root.left or root.right: ans = ans and root.val == x return ans return dfs(root) |
# class Tree:
# def __init__(self, val, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def solve(self, root):
def dfs(root):
if not root:
return True
x = 0
ans = True
if root.left:
ans = ans and dfs(root.left)
x += root.left.val
if root.right:
ans = ans and dfs(root.right)
x += root.right.val
if root.left or root.right:
ans = ans and root.val == x
return ans
return dfs(root)Remember, we can traverse the binary tree using Breadth First Search: Teaching Kids Programming – Breadth First Search Algorithm to Determine Sum Binary Tree
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: A Bash Process Controller to Start, Stop and Restart an Daemon Program
Next Post: Java's String Repeat Implementation
