算法训练营Day16(二叉树)

2023-12-14 22:58:21

今日内容:?

  • ?104.二叉树的最大深度??559.n叉树的最大深度
  • ?111.二叉树的最小深度
  • ?222.完全二叉树的节点个数

迭代法,大家可以直接过,二刷有精力的时候?再去掌握迭代法。

?104.二叉树的最大深度?

104. 二叉树的最大深度 - 力扣(LeetCode)

深度与高度

深度是往下数,前序遍历

高度是往上数,后续遍历

这道题我用后续遍历求根节点的高度,也就等于最大深度了。

前序遍历求最大深度,涉及到回溯的知识,后续二刷学完回溯的时候补充,以及迭代法

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

559. N 叉树的最大深度 - 力扣(LeetCode)

class Solution {
    public int maxDepth(Node root) {
        if(root==null){
            return 0;
        }
        int heigh = 0;
        if(root.children!=null){
            for(Node child:root.children){
                heigh = Math.max(heigh,maxDepth(child));
            }
        }
        return 1+heigh;
    }
}

111. 二叉树的最小深度 - 力扣(LeetCode)

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

222. 完全二叉树的节点个数 - 力扣(LeetCode)

普通二叉树解法

后序遍历做。

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

完全二叉树解法

利用完全二叉树特性,少遍历中间节点,只需要遍历树两侧的节点,因为完全二叉树中间的节点肯定存在

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        TreeNode left = root.left;
        TreeNode right = root.right;
        int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的,为了下面求指数方便
        while (left != null) {  // 求左子树深度
            left = left.left;
            leftDepth++;
        }
        while (right != null) { // 求右子树深度
            right = right.right;
            rightDepth++;
        }
        if(leftDepth==rightDepth){
            return (2<<leftDepth)-1;//2<<的话,本身就是2,所以又移子树深度相当于加一个父节点求完全二叉树
        }
        int leftNume = countNodes(root.left);
        int rightNum = countNodes(root.right);
        return 1+leftNume+rightNum;
    }
}

文章来源:https://blog.csdn.net/weixin_65728526/article/details/134999515
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。