剑指 树的深度

通过递归的方法，先去求左子树的路径长度，再去求右子树的路径长度，看哪一个路径长度大，则返回哪一条路径。

class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        if pHead==None:
            return None

        l=pHead
        while l!=None:
            node=RandomListNode(l.label)

            node.next=l.next
            l.next=node
            l=node.next


        s=pHead
        while s!=None and s.next!=None:
            if s.random:
                s.next.random=s.random.next
            s=s.next.next
        result=p=pHead.next
        #result=RandomListNode(0)
        f=pHead
        while p.next!=None:
            f.next=f.next.next
            p.next=p.next.next

            p=p.next
            f=f.next
        f.next=None
        return result

广度优先搜索，队列中加入一个level变量，注意的是在循环外初始化queue中加入level,在循环内也要记得加入。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import collections
class Solution:
    def TreeDepth(self, pRoot):
        # write code here
        if pRoot==None:
            return 0
        queue=collections.deque([(pRoot,0)])


        while queue:
            node,level=queue.popleft()
            level+=1
            if node.left:
                queue.append((node.left,level))
            if node.right:
                queue.append((node.right,level))

        return level