Day16:LeedCode 104.二叉树的最大深度 111.二叉树最小深度 222.完全二叉树的结点个数

104. 二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

思路:根结点最大深度=max(左子树最大深度,右子树最大深度)+1

终止条件,结点为null,该结点最大深度为0

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

}

111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

本题跟上题类似,但有差别

错误代码:

 与上一题求最大深度比,区别在这

当左右结点都不为空时: length=1+Math.min(minDepth(root.left),minDepth(root.right))

当左节点为空时:length=minDepth(root.right)+1

当右结点为空时:length=minDepth(root.left)+1

当根节点为空时:length=0;

class Solution {
    public int minDepth(TreeNode root) {
     if(root==null)
     return 0;
     if(root.left==null){
     return minDepth(root.right)+1;
     } else if (root.right==null){
     return minDepth(root.left)+1;
     }else{
    return 1+Math.min(minDepth(root.left),minDepth(root.right));
     }
    
    }
}

222. 完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

思路:

求普通二叉树结点个数:
结点个数=左子树结点个数+右子树结点个数+1

class Solution {
    public int countNodes(TreeNode root) {
    if(root==null)
    return 0;
    return countNodes(root.left)+countNodes(root.right)+1;
    }
}

我们可以把完全二叉树当成普通二叉树来求结点个数,但上面方法没利用完全二叉树的特性

完全二叉树的两种情况:

1.完全二叉树为满二叉树,结点个数总数= 2^树深度 - 1

2.完全二叉树不为满二叉树,但是其左子树或者右子树为满二叉树 ,满二叉树可以直接用公式计算结点个数,对于非满二叉树结点总数=左子树结点总数+右结点总数+1

这里关键在于如何去判断一个左子树或者右子树是不是满二叉树呢？

在完全二叉树中，如果递归向左遍历的深度等于递归向右遍历的深度，那说明就是满二叉树。如图：

递归三部曲:

1.确定返回值和参数,返回结点个数int 传入结点root

2.确认结束条件:当该子树为满二叉树为直接计算该子树结点总数

                          当该子树为Null时,结点个数为0

3.递归逻辑:当前子树结点个数=1+ countNodes(root.left)+countNodes(root.right)

class Solution {
    public int countNodes(TreeNode root) {
    if(root==null)return 0;
    int left_length=0;
    TreeNode leftN=root.left;
    while(leftN!=null){
        leftN=leftN.left;
        left_length++;
    }
    int right_length=0;
    TreeNode rightN=root.right;
    while(rightN!=null){
        rightN=rightN.right;
        right_length++;
            }
    if(right_length==left_length){
          return (2 <<  right_length) - 1;
    }
    return 1+ countNodes(root.left)+countNodes(root.right);
}
}