二叉树深度

递归方法

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def TreeDepth(self, pRoot):
        if pRoot is None:
            return 0
        left = self.TreeDepth(pRoot.left)
        right = self.TreeDepth(pRoot.right)
        depth = max(left, right) + 1
        return depth

非递归

按层遍历，利用辅助队列，每一层的节点加入，然后再层中遍历，弹出层中节点，加入层中节点的左右子节点，遍历完一层深度加一。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def TreeDepth(self, pRoot):
        # write code here
        if pRoot is None:
            return 0
        q = []
        depth = 0
        q.append(pRoot)
        while(len(q) > 0):  # 队列为空时说明没有下一层
            length = len(q)
            for i in range(length):  # 遍历层的每个节点看是否有子节点有则加入
                current = q.pop(0)  # current为当前遍历到的层中节点，取出，注意pop(-1)为默认，这里要pop(0),取出第一个，先入先出
                if current.left:
                     q.append(current.left)
                if current.right:
                    q.append(current.right)
            depth += 1
        return depth