tree

二叉树的遍历

深度（纵向）优先在Python中一般使用列表，广度优先（横向）一般使用迭代# 617. Merge Two Binary Trees

235 Lowest Common Ancestor of a Binary Search Tree
236 Lowest Common Ancestor of a Binary Tree
找最近的树祖先问题（235是二叉搜索树BST）

235的思路就是，把左右两个值和root比较，可以用递归也可以不用(while root)~
236就复杂很多，是我写不出来的level了，只会用递归实现，我的理解是，从root开始，往左往右去找，是不是有p、q出现，有的话就赋值，最后判断是否为空。都不为空就最好啦，他们分开的时候（root）就是最近祖先，有一个为空，p、q应该在左or右一边，所以最先找到的那个节点就是最近祖先了（直接return left or right）。

236代码

深度

def depth(tree):
    if tree==None:
        return 0
    left,right=depth(tree.left),depth(tree.right)
    return max(left,right)+1

前序 根左右

def pre_order(tree):
    if tree==None:
        return
    print tree.data
    pre_order(tree.left)
    pre_order(tree.right)

中序 左根右

def depth(tree):
    if tree==None:
        return 0
    left,right=depth(tree.left),depth(tree.right)
    return max(left,right)+1

后序 左右根

def post_order(tree):
    if tree==None:
        return
    post_order(tree.left)
    post_order(tree.right)   
    print tree.data