题解 | #二叉树的深度 01 02#

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/


import java.util.*;

public class Solution {
    public int TreeDepth(TreeNode root) {
        if (root == null) return 0;
        int res = 0;
        // 队列实现bfs
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        // 遍历每一层
        while (!queue.isEmpty()) {
            // 每遍历一层,计数+1
            res++;
            // queue每次只保存当层的节点数
            int size = queue.size();
            // 遍历当前层的每一个节点, 队列中poll掉当前层节点,add其所有子节点
            for (int i = 0; i < size; i++) {
                // 取出当前节点,并将其左右子节点放入队列
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return res;
    }

    /*
     public int TreeDepth (TreeNode root) {
        //空节点没有深度
        if (root == null)
            return 0;
        //返回子树深度+1
        return Math.max(TreeDepth(root.left), TreeDepth(root.right)) + 1;
    }
    */
}

01:

主要思路：利用队列，完成层序遍历

算法流程：

• new一个队列，用于保存每一层的节点，实现bfs
• 遍历每一层，每遍历一层, 计数+1
• queue每次只保存当层的节点数
• 遍历当前层的每一个节点, 队列中poll掉当前层节点, add其所有子节点
• 取出当前节点,并将其左右子节点放入队列

02：

递归终止条件： 递归到叶子节点

返回值：返回当前节点的深度

递归函数功能：递归函数功能：获取当前节点 root 的深度

算法流程：

• 本质上是对树作后序遍历
• 每次递归每个节点 root 的左右子树，并且只得到左右子树中较大的子树深度。
• 当前节点 root 左右子树递归到叶子节点后，root == null，递归开始自底向上返回，每次向上 return 都 + 1, 即深度 + 1