Solution to LeetCode 222 Count Complete Tree Nodes, LeetCode 110 Balanced Binary Tree, and LeetCode 257 Binary Tree Paths.
LeetCode 222
Count Complete Tree Nodes (Medium) [link]
1] BFS. Level-order traversal. Iterative solution.
Time complexity O(n). Space complexity O(n).
# 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 countNodes(self, root: Optional[TreeNode]) -> int:
que = deque([root])
cnt = 0
if not root:
return cnt
while que:
size = len(que)
for i in range(size):
cur = que.popleft()
cnt += 1
if cur.left:
que.append(cur.left)
if cur.right:
que.append(cur.right)
return cnt
2] DFS. Recursive solution.
# 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 countNodes(self, root: Optional[TreeNode]) -> int:
def dfs(node):
if not node:
return 0
leftnum = dfs(node.left)
rightnum = dfs(node.right)
return leftnum + rightnum + 1
return dfs(root)
# 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 countNodes(self, root: Optional[TreeNode]) -> int:
if not root: return 0
return self.countNodes(root.left)+self.countNodes(root.right)+1
LeetCode 110
Balanced Binary Tree. (Easy) [link]
Note the difference between term “depth” and “height” of tree node. ‘depth’ is measured from the root while ‘height’ is measured from leaf.
**Bottom up. Recursion solution. Post-order traversal. **
The recursion function returns the max height (i.e. max(left_height + right_height)+1) of the currently root if the height difference < 2. It returns -1 if the height difference is >= 2.
The recursion terminates and returns 0 when it reaches to leaf, or terminates and returns -1 when left or right tree returns -1.
Time complexity O(n). Space complexity O(n).
# 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 isBalanced(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
def get_height(node):
if not node:
return 0
leftHeight = get_height(node.left)
rightHeight = get_height(node.right)
if leftHeight == -1: # left
return -1
if rightHeight == -1: # right
return -1
if abs(leftHeight - rightHeight) > 1: # root
return -1
else:
return 1 + max(leftHeight, rightHeight)
return get_height(root) != -1
Iterative method is feasible but not suitable.
LeetCode 257
Binary Tree Paths (Easy) [link]
1] Pre-order traversal. Backtracking. Recursion.
Time complexity O(n^2). It takes O(n) to traverse all the node once and takes O(n) to construct path whenever traverse to new node.
Space complexity O(n^2). The space taken by path is O(1 + 2 + …+ n) = O(n^2).
# 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 binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
path = ''
result = []
if not root: return result
self.traversal(root, path, result)
return result
def traversal(self, root, path, result):
path += str(root.val)
if not root.left and not root.right:
result.append(path)
if root.left:
self.traversal(root.left, path + '->', result)
if root.right:
self.traversal(root.right, path + '->', result)
2] Pre-order traversal. Iterative method using Stack. One stack stores the current node, the other stack stores the current path.
# 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 binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
stack = [root]
cur_path = [str(root.val)]
result = []
while stack:
cur = stack.pop()
path = cur_path.pop()
if not cur.left and not cur.right:
result.append(path)
if cur.right:
stack.append(cur.right)
cur_path.append(path+'->'+ str(cur.right.val))
if cur.left:
stack.append(cur.left)
cur_path.append(path+'->'+ str(cur.left.val))
return result
3] Pre-order traversal. Iterative method using Queue. One queue stores the current node, the other queue stores the current path.
# 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 binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
que = deque()
que.append(root)
cur_path = deque()
cur_path.append(str(root.val))
result = []
while que:
cur = que.popleft()
path = cur_path.popleft()
if not cur.left and not cur.right:
result.append(path)
if cur.left:
que.append(cur.left)
cur_path.append(path+'->'+ str(cur.left.val))
if cur.right:
que.append(cur.right)
cur_path.append(path+'->'+ str(cur.right.val))
return result
Note that the order of appending left node and right node does not matter. But if we strictly follow the pre-order traversal (root -> left -> right). When using stack, append right child first. When using queue, append left child first.
