算法训练营Day16(二叉树)

?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;
    }
}