【剑指Offer】038——二叉树的深度 （树）

题目描述

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

解题思路

法一：递归法。求二叉树的深度，就是求左子树、右子树的中深度最大的加上一个根节点，依此递归即可。
法二：层次遍历。每遍历一层，deep 加 1，直接到最后一层，输出 deep。

参考代码

Java

import java.util.Queue;
import java.util.LinkedList;
class TreeNode {
     int val = 0;
     TreeNode left = null;
     TreeNode right = null;
     public TreeNode(int val) {
        this.val = val;
    }
 }
public class Solution {
    // 递归法
    public int TreeDepth(TreeNode root) {
        if (root == null) return 0;
        int left = TreeDepth(root.left) + 1; // +1 表示加上当前结点
        int right = TreeDepth(root.right) + 1;
        return left > right ? left:right;
    }
    // 层次遍历
    public int TreeDepth2(TreeNode root) {
        if (root == null) return 0;
        int deep = 0;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();   // 用队列存储下一层的结点
        queue.offer(root); // 将根压入队列
        int start = 0, end = 1; // 用于控制每一层的结束，end也可以看成
        while (!queue.isEmpty()){
            TreeNode node = queue.poll(); // 队列逐次弹出结点
            start ++; // 层数添加
            if (node.left != null) queue.offer(node.left); // 为下一层添加node
            if (node.right != null) queue.offer(node.right);// 为下一层添加node
            // 判断当前层是否已经结束
            if (start == end){
                end = queue.size();
                start = 0;
                deep ++;
            }
        }
        return deep;
    }
}

Python

# -*- 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 not pRoot:return 0
        left = self.TreeDepth(pRoot.left) + 1
        right = self.TreeDepth(pRoot.right) + 1
        return left if left > right else right

个人订阅号

image