【算法刷题day16】Leetcode:104. 二叉树的最大深度、111. 二叉树的最小深度、222.完全二叉树的节点个数

草稿图网站
java的Deque

Leetcode 104. 二叉树的最大深度

题目：104. 二叉树的最大深度
解析：代码随想录解析

解题思路

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
 //递归
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null)
            return 0;
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

//队列，但是时间很慢
class Solution {
    public int maxDepth(TreeNode root) {
        int depth = 0;
        if (root == null)
            return depth;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            depth++;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null)  queue.add(node.left);
                if (node.right != null)  queue.add(node.right);
            }
        }
        return depth;
    }
}

//栈，但是时间很慢

总结

递归没写过

Leetcode 111. 二叉树的最小深度

题目：111. 二叉树的最小深度
解析：代码随想录解析

解题思路

找到第一个叶子节点就可以返回值

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
//递归

//队列，层序遍历
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null)
            return 0;
        int depth = 0;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            depth++;
            for (int i = 0; i < size; i++){
                TreeNode node = queue.poll();
                if (node.left == null && node.right == null)
                    return depth;
                if (node.left != null)  queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }
        return depth;
    }
}

//递归
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
//递归
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null)
            return 0;
//        if (root.left == null && root.right == null)
//            return 1;
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        leftDepth = leftDepth == 0 ? rightDepth : leftDepth;
        rightDepth = rightDepth == 0 ? leftDepth : rightDepth;
        return Math.min(leftDepth, rightDepth) + 1;
    }
}

总结

暂无

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

题目：222.完全二叉树的节点个数
解析：代码随想录解析

解题思路

遍历

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
 //递归
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) {
        int count = 0;
        if (root == null)
            return count;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size;  i++) {
                TreeNode node = queue.poll();
                count++;
                if (node.left != null)  queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }
        return count;
    }
}

总结

暂无