Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Something worth noticing in the problem:

a. It is a binary tree

b. only if there is a "root-to-leaf" path , is it a valid path

              5
             / \    given this tree and sum = 5, it is not a valid path since 
            4   8   it doesn't get down to the leaf.

It is clearly a recursive problem. Pass the current required sum to certain root until the leaf and see whether it is a valid path

# Definition for a  binary tree node
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    # @param root, a tree node
    # @param sum, an integer
    # @return a boolean

    def hasPathSum(self, root, sum):
        if root is None:
             return False
        if root.val == sum and root.left is None and root.right is None:
            return True
        if root.val != sum and root.left is None and root.right is None:
            return False
        else:
            return self.hasPathSum(root.left,sum-root.val) or self.hasPathSum(root.right, sum-root.val)

Balanced Binary Tree

Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

The same question appears on <Cracking> too (p86 4.1)

The key points to this problem is:

a.  check whether the current tree is balanced 
     i.e., |height(left sub tree) - height(right sub tree)| <= 1

b. check whether the left sub tree and right sub tree of the current tree is balanced
    It could be the case that even though the left, right height of the current tree differs no more 
    than one, the two trees are not balanced by themselves. e.g. the left sub tree could only 
    have left child and is an array...>__<

c. what is the height of the current tree ?
    height of the current tree is the maximum height of left and right sub tree + 1
    (even by wording, it is recursive in nature haha)

Something worth noticing:

a. since there are recursions in the process, it could lead to duplicates recursion. 
     notice that when you are calculating the height of the current tree, you actually already
     calculate the height of its left and right sub trees.  Use a DP :)

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    # @param root, a tree node
    # @return a boolean
    def __init__(self):
        self.dp = {}

    def height(self, root):
        if root is None:
            return 0
        else:
            lh, rh = self.height(root.left), self.height(root.right)
            rh = max(lh, rh) + 1
            self.dp[root.left], self.dp[root.right] =lh, rh
        return h

    def isBalanced(self, root):
        if root is None:
            return True
        else:
            # this checks 1.whether is current tree is balanced; 2. whether its two sub trees are balanced
            return abs(self.height(root.left)-self.height(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)