[刷题记录Day16]Leetcode二叉树

番茄随想 / 2023-08-26 / 原文

No.1

题目

二叉树的最大深度

思路

递归
其实是后序遍历的方式

代码

public int maxDepth(TreeNode root) {  
    if (root == null)  
        return 0;  
  
    return Math.max(1 + maxDepth(root.left), 1 + maxDepth(root.right));  
}

No.2

题目

二叉树的最小深度

思路

递归
最小深度是指根节点到叶子节点的距离
遇到其中一个左右子树缺失的情况要特殊处理，不与缺失的子树比较深度

代码

public int minDepth(TreeNode root) {  
    if (root == null)  
        return 0;  
  
    int minLeftDepth = minDepth(root.left);  
    int minRightDepth = minDepth(root.right);  
  
    // 只需要处理其中一个子树缺失的情况就可以了  
    // 缺失就返回另一颗子树的深度  
    if (minLeftDepth == 0 && minRightDepth !=0)  
        return 1 + minRightDepth;  
    if (minRightDepth == 0 && minLeftDepth != 0)  
        return 1 + minLeftDepth;  
  
    // 能兼容：1. 左右子树深度都不为0的情况 2. 左右子树深度都为0的情况  
    return 1 + Math.min(minLeftDepth, minRightDepth);  
}

No.3

题目

完全二叉树的节点个数

思路

深度优先搜索之后序遍历
没啥特别的

代码

public int traverse(TreeNode node) {  
    if (node == null)  
        return 0;  
  
    int leftNum = traverse(node.left);  
    int rightNum = traverse(node.right);  
    return 1 + leftNum + rightNum;  
}  
  
public int countNodes(TreeNode root) {  
    int count = 0;  
    if (root == null)  
        return count;  
  
    count = traverse(root);  
  
    return count;  
}