二叉树

二叉树的最大深度

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

之前用一种较为曲折的方式解二叉树的层序遍历时貌似已经实现过求二叉树的最大深度。最容易想到的还是递归。

import static java.lang.Math.max;

class Solution {
    public int maxDepth(TreeNode root) {
        return digSeek(root, 0);
    }

    public int digSeek(TreeNode node, int depth) {
        if(node == null) return depth;
        int left = 0;
        int right = 0;
        if(node.left != null) {
            left = digSeek(node.left, depth + 1);
        }
        if(node.right != null) {
            right = digSeek(node.right, depth + 1);
        }
        return max(max(left, right), depth+1);
    }
}

以上这种递归好像还不是典型的递归，典型递归的代码似乎能更简洁些。

import static java.lang.Math.max;

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

优雅，实在是太优雅了。

再尝试用迭代做一做，层序遍历的方法。

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        Queue<TreeNode> list = new LinkedList<>();
        list.offer(root);
        int n = 0;
        while(!list.isEmpty()) {
            int size = list.size();
            for(int i = 0; i < size; i++) {
                TreeNode node = list.poll();
                if (node.left != null) {
                    list.offer(node.left);
                }
                if (node.right != null) {
                    list.offer(node.right);
                }
            }
            n++;
        }
        return n;
    }
}

二叉树的最小深度

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

和求最大深度的区别，求最小深度不需要遍历每个节点，我们是比小，往深最先结束的就是最小

这里用递归的话会有冗余，因为递归是深度优先的，会遍历一些没必要的节点。所以我这里采用层序遍历的方式，用队列实现

class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        Queue<TreeNode> list = new LinkedList<>();
        list.offer(root);
        int n = 0;
        while(!list.isEmpty()) {
            int size = list.size();
            for(int i = 0; i < size; i++) {
                TreeNode node = list.poll();
                if (node.left == null && node.right == null) {
                    return n + 1;
                }
                if (node.left != null) {
                    list.offer(node.left);
                }
                if (node.right != null) {
                    list.offer(node.right);
                }
            }
            n++;
        }
        return n;
    }
}

递归的方式也尝试一下吧

import static java.lang.Math.max;
import static java.lang.Math.min;
class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        int left = 0;
        if (root.left != null) {
            left = minDepth(root.left);
        }
        int right = 0;
        if (root.right != null) {
            right = minDepth(root.right);
        }
        if (left == 0 || right == 0) {
            return max(left, right)+1;
        }
        return min(left, right)+1;
    }
}

需要注意的是，一般情况下我们是这样一个逻辑，最小深度等于左子树和右子树中深度小的那个加一min(left, right)+1，但是有一种情况例外，如果左子树和右子树中有一支为空，那么就应该是不为空的子树最小深度加一，我简略写为max(left, right)+1

看解析的时候还看到它的递归和我的有些不同

class Solution {
    int depth = 0;
    Integer minDepth = Integer.MAX_VALUE;
    public int minDepth(TreeNode root) {
        digSeek(root);
        return (minDepth == Integer.MAX_VALUE)? 0: minDepth;
    }

    public void digSeek(TreeNode node) {
        depth++;
        if(node == null) {
            depth--;
            return ;
        }
        if(node.left == null && node.right == null) {
            minDepth = Math.min(depth, minDepth);
        }
        digSeek(node.left);
        digSeek(node.right);
        depth--;
    }
}

它的深度是全局唯一的，随着遍历而动，在遍历的过程中遇到叶子节点就尝试更新一下最小值，一开始取得是最大值，需要注意的是，如果最后minDepth依然是最大值，那么说明一开始的root就是null，返回0。

参考链接：

【代码随想录】https://www.programmercarl.com/0104.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%A4%A7%E6%B7%B1%E5%BA%A6.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE