二叉树的最大深度

题目描述

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的距离。

思路

分治法。
求最大深度，当前节点左子节点的最大深度和右子节点的最大深度的较大值加一，就是将当前结点作为root的深度
所以，对每个节点：
递归左子节点得到一个深度，递归右子节点得到一个深度，然后区最大值+1，返回给自己的父节点

代码

public int maxDepth(TreeNode root) {
        // write your code here
        if(root == null) {
            return 0;
        }
        return getDepth(root, 1);
    }
    
    private int getDepth(TreeNode root, int num) {
        int leftNum = num;
        int rightNum = num;
        if(root.left != null) {
            leftNum = getDepth(root.left, num+1);
        }
        if(root.right != null) {
            rightNum = getDepth(root.right, num+1);
        }
        return Math.max(leftNum, rightNum);
    }

考察点

• 二叉树
• 分治法