Skip to content

Instantly share code, notes, and snippets.

@dapangmao

dapangmao/tree.md

Last active August 29, 2015 14:05
Show Gist options
  • Save dapangmao/e9ccb64523f4e0a0e7eb to your computer and use it in GitHub Desktop.
Save dapangmao/e9ccb64523f4e0a0e7eb to your computer and use it in GitHub Desktop.
Download ZIP
Trees
Raw
tree.md
  • The class to create tree
class TreeNode:
    def __init__(self, val):
        self.left = None
        self.right = None
        self.val = val

def to_root(input):
    a = [TreeNode(i) if i != '#' else None for i in input]
    rst, tmp, carry, current = [], [], [], []
    cnt = 0
    for i in range(len(a)):
        tmp.append(a[i])
        if len(tmp) == 2*cnt or i in [len(a)-1, 0]:
            rst.append(tmp)
            cnt = sum(map(lambda x: 0 if x is None else 1, tmp))
            tmp = []
    for layer in rst:
        current = iter(layer)
        for node in carry:
            if node:
                try:
                    node.left = next(current)
                    node.right = next(current)
                except:
                    pass
        carry = layer
    return rst[0][0]
#-------------------------------------------------------------------------------
# Name:        Binary Tree Level Order Traversal
# Purpose:
#        Given a binary tree, return the level order traversal
#        of its nodes' values. (ie, from left to right,
#        then right to left for the next level and alternate between).
#
#        Given binary tree {3,9,20,#,#,15,7},
#            3
#           / \
#          9  20
#            /  \
#           15   7
#        
#        return its level order traversal as:
#        [
#          [3],
#          [9,20],
#          [15,7]
#        ]
#-------------------------------------------------------------------------------
def levelOrder(root):
    if root is None:
        return []
    current = [root]
    rst = []
    while current: # Driven by the size of root
        elements, tmp = [], []
        for node in current:
            elements.append(node.val)
            if node.left:
                tmp.append(node.left) 
            if node.right:
                tmp.append(node.right)
        rst.append(elements)
        current = tmp
    return rst

root = to_root([3,9,20,'#','#',15,7, 1, 2, 3, '#', 5, 6])
print levelOrder(root)

#-------------------------------------------------------------------------------
# Name:       Binary Tree Inorder Traversal
# Purpose:
#
#        Given a binary tree, return the inorder traversal of its nodes' values.
#        For example:
#        Given binary tree {1,#,2,3},
#          1
#            \
#             2
#            /
#           3
#        return [1,3,2].
#-------------------------------------------------------------------------------
def inorderTraversal2(root):
    if root is None:
        return []
    return inorderTraversal2(root.left) + [root.val] + inorderTraversal2(root.right)

def inorderTraversal(root):
    rst = []
    stack = []
    current = root
    while current or stack:
        if current:
            stack.append(current)
            current = current.left
        else:
            node = stack.pop()
            rst.append(node.val)
            current = node.right
    return rst

root = to_root([1, '#', 2, 3])
print inorderTraversal2(root)
print inorderTraversal(root)

#-------------------------------------------------------------------------------
# Name:      Binary Tree Preorder Traversal
# Purpose:
#
#        Given a binary tree, return the inorder traversal of its nodes' values.
#        For example:
#        Given binary tree {1,#,2,3},
#          1
#            \
#             2
#            /
#           3
#        return [1,2,3 ].
#-------------------------------------------------------------------------------
def preorderTraversal2(root):
    if root is None:
        return []
    return [root.val] + preorderTraversal2(root.left) + preorderTraversal2(root.right)

#-------------------------------------------------------------------------------
# Name:      Binary Tree Postorder Traversal
# Purpose:
#
#        Given a binary tree, return the inorder traversal of its nodes' values.
#        For example:
#        Given binary tree {1,#,2,3},
#          1
#            \
#             2
#            /
#           3
#        return [1,3,2].
#-------------------------------------------------------------------------------
def postorderTraversal2(root):
    if root is None:
        return []
    return postorderTraversal2(root.left) + postorderTraversal2(root.right) + [root.val]
    
#-------------------------------------------------------------------------------
# Name:        Same Tree
# Purpose:
#
#        Given two binary trees, write a function to check if they are equal or not.
#        Two binary trees are considered equal if they are structurally
#        identical and the nodes have the same value.
#-------------------------------------------------------------------------------
def isSameTree(a, b):
    if a is None and b is None:
        return True
    if None in [a, b] or a.val != b.val:
        return False
    return isSameTree(a.left, b.left) and isSameTree(a.right, b.right)

#-------------------------------------------------------------------------------
# Name:        subTree
# Purpose:    From Career Cup
#
#        You have two very large binary trees: T1, with millions of nodes,
#        and T2, with hundreds of nodes. Create an algorithm
#        to decide if T2 is a subtree of T1.
#-------------------------------------------------------------------------------
def subTree(big, small):
    if isSameTree(big, small):
       return True
    if big is None:
       return False
    return subTree(big.left, small) or subTree(big.right, small)
    
#-------------------------------------------------------------------------------
# Name:        Maximum Depth of Binary Tree
# Purpose:
#         Given a binary tree, find its maximum depth.
#        The maximum depth is the number of nodes along the longest
#        path from the root node down to the farthest leaf node.
#-------------------------------------------------------------------------------
def maxDepth(root, rst = 0):
    if root is None:
        return rst
    if root.left and root.right is None:
        return maxDepth(root.left, rst+1)
    if root.right and root.left is None:
        return maxDepth(root.right, rst+1)
    return max(maxDepth(root.left, rst+1), maxDepth(root.right, rst+1))


test1 = to_root([5, 4, 8, 11, '#', 13, 4, 7, 2, '#', '#', 5, 1, 9, 9])
print maxDepth(test1)

#-------------------------------------------------------------------------------
# Name:        Minimum  Depth of Binary Tree
# Purpose:
#
#         Given a binary tree, find its maximum depth.
#        The minimum  depth is the number of nodes along the longest
#        path from the root node down to the farthest leaf node.
#-------------------------------------------------------------------------------
def minDepth(root, rst = 0):
    if root is None:
        return rst
    if root.left and root.right is None:
        return minDepth(root.left, rst+1)
    if root.right and root.left is None:
        return minDepth(root.right, rst+1)
    return min(minDepth(root.left, rst+1), minDepth(root.right, rst+1))
    
test1 = to_root([5, 4, 8, 11, '#', 13, 4, 7, 2, '#', '#', 5, 1, 9, 9])
print minDepth(test1)

#-------------------------------------------------------------------------------
# Name:        Symmetric Tree
# Purpose:
#
#        Given a binary tree, check whether it is a mirror of itself
#        (ie, symmetric around its center).
#        For example, this binary tree is symmetric:
#            1
#           / \
#          2   2
#         / \ / \
#        3  4 4  3
#
#        But the following is not:
#            1
#           / \
#          2   2
#           \   \
#           3    3
#-------------------------------------------------------------------------------
def isSymmetric(root):
    if root is None:
        return True
    return _isSymmertric(root.left, root.right)

def _isSymmertric(left, right):
    if left is None and right is None:
        return True
    if left is None or right is None or left.val != right.val:
        return False
    return _isSymmertric(left.left, right.right) and \
        _isSymmertric(left.right, right.left)
    
root = to_root([1, 2, 2, 3, 4, 4, 3])
print isSymmetric(root)

#-------------------------------------------------------------------------------
# Name:        Path Sum
# Purpose:
#
#        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.
#-------------------------------------------------------------------------------
def hasPathSum(root, sum):
    if root is None:
        return False
    if root.left is None and root.right is None and sum == root.val:
        return True
    return hasPathSum(root.left, sum - root.val) or \
        hasPathSum(root.right, sum - root.val)

root = to_root([5, 4, 8, 11, '#', 13, 4, 7, 2, '#', '#', '#', 1])
print hasPathSum(root, 22)

#-------------------------------------------------------------------------------
# Name:        Path Sum II 
# Purpose:
#
#        Given a binary tree and a sum, find all root-to-leaf
#        paths where each path's sum equals the given sum.
#
#        For example:
#        Given the below binary tree and sum = 22
#
#              5
#             / \
#            4   8
#           /   / \
#          11  13  4
#         /  \    / \
#        7    2  5   1
#-------------------------------------------------------------------------------
class Solution:
    def pathSum(self, root, sum):
        return self._pathSum([], root, sum)

    def _pathSum(self, current, root, sum):
        if root is None:
            return []
        if root.left is None and root.right is None and root.val == sum: 
            return [current + [root.val]]
        return self._pathSum(current + [root.val], root.left, sum - root.val) + \
            self._pathSum(current + [root.val], root.right, sum - root.val)

a = Solution()
root = to_root([5, 4, 8, 11, '#', 13, 4, 7, 2, '#', '#', 5, 1])
print a.pathSum(root, 22)

#-------------------------------------------------------------------------------
# Name:        Validate Binary Search Tree
# Purpose:
#
#        Given a binary tree, determine if it is a valid binary search tree (BST).
#
#        Assume a BST is defined as follows:
#
#        The left subtree of a node contains only nodes with keys
#        less than the node's key.
#        The right subtree of a node contains only nodes with keys
#        greater than the node's key.
#        Both the left and right subtrees must also be binary search trees.
#
#-------------------------------------------------------------------------------
def isValidBST(root, lo = -2147483647, hi = 2147483647): # from sys import maxint
    if root is None: 
        return True
    if root.val <= lo or root.val >= hi:
        return False
    return isValidBST(root.left, lo, root.val) and isValidBST(root.right, root.val, hi)

test1 = to_root([4, 2, 5, 1, 3, '#', 6])
print isValidBST(test1)

def isValidBST2(root):
    carry = -2147483647
    for x in inorderTraversal2(root):
        if x <= carry:
            return False
        carry = x
    return True
print isValidBST2(test1)

#-------------------------------------------------------------------------------
# Name:        Convert Sorted Array to Binary Search Tree
# Purpose:
#
#        Given an array where elements are sorted in
#        ascending order, convert it to a height balanced BST.
#-------------------------------------------------------------------------------
def sortedArrayToBST(arr):
    return _sortedArrayToBST(arr, 0, len(arr)-1)

def _sortedArrayToBST(arr, lo, hi):
    if lo > hi:
        return None
    mid =(lo + hi)/2
    root = TreeNode(arr[mid])
    root.left = _sortedArrayToBST(arr, lo, mid-1)
    root.right = _sortedArrayToBST(arr, mid+1, hi)
    return root

a = [1, 2, 3, 4, 5, 6, 7, 8]
b = [1]
root = sortedArrayToBST(a)
print inorderTraversal2(root)
root = sortedArrayToBST(b)
print inorderTraversal2(root)

#-------------------------------------------------------------------------------
# Name:        Sum Root to Leaf Numbers
# Purpose
#    Given a binary tree containing digits from 0-9 only,
#    each root-to-leaf path could represent a number.
#    An example is the root-to-leaf path 1->2->3
#    which represents the number 123.
#-------------------------------------------------------------------------------
def sumNumbers(self, root, rst = 0):
    if root is None:
        return 0
    if root.right is None and root.left is None:
        return rst*10 + root.val
    return self.sumNumbers(root.left, rst*10 + root.val) + \
        self.sumNumbers(root.right, rst*10 + root.val)
        
#-------------------------------------------------------------------------------
# Name:        Populating Next Right Pointers in Each Node
# Purpose:
#             1 -> NULL
#           /  \
#          2 -> 3 -> NULL
#         / \  / \
#        4->5->6->7 -> NULL
#-------------------------------------------------------------------------------
# Definition for a  binary tree node
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        self.next = None

class Solution:
    def connect(self, root):
        if root is None:
            return None
        if root.left:
            root.left.next = root.right
        if root.right and root.next:
            root.right.next = root.next.left
        self.connect(root.left)
        self.connect(root.right)
  • Need an assistant function
#-------------------------------------------------------------------------------
# Name:        Balanced Binary Tree
# Purpose:
#       Given a binary tree, determine if it is height-balanced.
#       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.
#-------------------------------------------------------------------------------
class Solution:
    def isBalanced(self, root):
        if root is None:
            return True
        if abs(self.depth(root.left) - self.depth(root.right)) > 1:
            return False
        return self.isBalanced(root.left) and self.isBalanced(root.right)

    def depth(self, root):
        if root is None:
            return 0
        return 1 + max(self.depth(root.left), self.depth(root.right))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment