二叉树的最大深度问题 / leeCode 104题

小半 • 2023年2月3日上午10:55 • 技术随笔 • 阅读 75

一.概念

深度：树的根节点到最远叶子结点的最长路径上的结点数，即层数

二.方法

1.如果根结点为空，则最大深度为0；
2.计算左子树的最大深度；
3.计算右子树的最大深度；
4.当前树的最大深度max=左子树的最大深度maxL和右子树的最大深度maxR中的较大者+1

代码：

 public int maxDepth() { //计算整个树的最大深度
        return maxDepth(root);
    }

 private int maxDepth(Node x) { //计算指定树的最大深度
        int max = 0;  //当前最大
        int maxL = 0;  //左子树最大
        int maxR = 0;  //右子树最大    
        
	//安全校验
        if (x == null) {//仅作为安全校验，并非递归出口
            return 0;
        }
       
        //计算左子树的最大深度
        if (x.left != null) {
            maxL = maxDepth(x.left); //return的max赋给了maxL
        }

        //计算右子树的最大深度
        if (x.right != null) {
            maxR = maxDepth(x.right); //return的max赋给了maxR
        }
        //比较左、右子树最大深度，取较大值+1作为max
        max = maxL > maxR ? maxL + 1 : maxR + 1;
        return max;
    }

思路：使用递归，当前最大结点为左右子结点中的最大值+1；
在这里若先判断是否有左右结点，则if (x == null) { return 0; } 只是安全校验，若没有判断是否有左右结点，则该代码块为递归出口，如：

    //最大深度问题
    public int maxDepth() { //计算整个树的最大深度
        return maxDepth(root);
    }

    private int maxDepth(Node x) { //计算指定树的最大深度
        //安全校验
        if (x == null) {//递归出口
            return 0;
        }
        int max = 0;  //当前最大
        int maxL = 0;  //左子树最大
        int maxR = 0;  //右子树最大


        //计算左子树的最大深度
            maxL = maxDepth(x.left); //return的max赋给了maxL
   
        //计算右子树的最大深度
            maxR = maxDepth(x.right);

        //比较左、右子树最大深度，取较大值+1作为max
        max = maxL > maxR ? maxL + 1 : maxR + 1;
        return max;
    }