剑指offer | 55 - I. 二叉树的深度

我就是我 2022-12-28 00:50 98阅读 0赞

**题目内容：**

> 输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

**例如：**

给定二叉树 [3,9,20,null,null,15,7]，
    
        3
       / \
      9  20
        /  \
       15   7
    
    返回它的最大深度 3 。

**提示：**

节点总数 <= 10000

--------------------

**方法一：** DFS深搜也就是树的后续遍历，找到左右子树最深的那个的深度再加上root的1就可以。DFS往往用递归或者栈来实现。

**方法二：** 层序遍历，也叫广搜BFS，往往用队列与while循环实现。

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    class Solution { 
    public:
        int maxDepth(TreeNode* root) { 
            if (!root) { 
                return 0;
            }
    
            queue<TreeNode*> bfs;
            bfs.push(root);
            int res = 0;
    
            while (!bfs.empty()) { 
                // 第一层循环确保当前层还有元素
                queue<TreeNode*> temp; // temp 用于储存当前层的下一层的所有元素
    
                while (!bfs.empty()) { 
                    // 第二层循环则是遍历当前层的所有元素
                    if (bfs.front() -> left) { temp.push(bfs.front() -> left);}
                    if (bfs.front() -> right) { temp.push(bfs.front() -> right);}
                    bfs.pop();
                }
    
                ++ res; // 层数 +1
                bfs = temp; // bfs 更新到当前层的下一层
            }
    
            return res;
        }
    };

参考：[字节题库 - \#剑55-I - 简单 - 二叉树的深度 - 2刷][- _55-I - _ - _ - 2]

[- _55-I - _ - _ - 2]: https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/solution/zi-jie-ti-ku-jian-55-i-jian-dan-er-cha-s-9gmt/