0531核心代码编程-企业内部门的最大层级-100分-编程实验室

题目描述：企业的组织架构以树形结构表示，每个节点包含：
left: 左子部门（第一个子部门）
right 右子部门（第二个子部门）
为了优化管理结构，实现扁平化管理，需要计算企业的最大管理层级深度。
请计算企业的部门层级的最大深度。
注意：
1、一个部门最多能有2个直属的子部门（二叉树）;
2、输入由数字和特殊符号＃组成的序列，总结点数不超过1024个；数字表示该位置有子部门，＃表示该位置无子部门（即无此节点）。

示例1
输入：["1","#","2","#","3","#","4","#","5"]
输出：5

示例2
输入：["1","2","3","4","5","6","7","8","9"]
输出：4

示例3
输入：["1","2","#"]

输出：2

根据题目要求，计算企业的部门层级最大深度，即二叉树的最大深度。输入为层序遍历序列（包含空节点"#"），需重建二叉树后计算深度。以下为各语言实现：

C++

#include <queue> #include <vector> #include <string> #include <algorithm> using namespace std; int max_depth(vector<string>& arr) { if (arr.empty() || arr[0] == "#") return 0; int n = arr.size(); int next_index = 1; queue<int> depths; depths.push(1); int max_depth = 1; while (!depths.empty() && next_index < n) { int depth = depths.front(); depths.pop(); for (int i = 0; i < 2; i++) { if (next_index >= n) break; if (arr[next_index] != "#") { int child_depth = depth + 1; max_depth = max(max_depth, child_depth); depths.push(child_depth); } next_index++; } } return max_depth; }

Java

import java.util.*; class Solution { public int max_depth(String[] arr) { if (arr.length == 0 || "#".equals(arr[0])) return 0; int n = arr.length; int nextIndex = 1; Queue<Integer> depths = new LinkedList<>(); depths.add(1); int maxDepth = 1; while (!depths.isEmpty() && nextIndex < n) { int depth = depths.poll(); for (int i = 0; i < 2; i++) { if (nextIndex >= n) break; if (!"#".equals(arr[nextIndex])) { int childDepth = depth + 1; maxDepth = Math.max(maxDepth, childDepth); depths.add(childDepth); } nextIndex++; } } return maxDepth; } }

JavaScript

function max_depth(arr) { if (arr.length === 0 || arr[0] === '#') return 0; const n = arr.length; let nextIndex = 1; const depths = [1]; let maxDepth = 1; while (depths.length > 0 && nextIndex < n) { const depth = depths.shift(); for (let i = 0; i < 2; i++) { if (nextIndex >= n) break; if (arr[nextIndex] !== '#') { const childDepth = depth + 1; maxDepth = Math.max(maxDepth, childDepth); depths.push(childDepth); } nextIndex++; } } return maxDepth; }

Go

package main func max_depth(arr []string) int { if len(arr) == 0 || arr[0] == "#" { return 0 } n := len(arr) nextIndex := 1 depths := []int{1} maxDepth := 1 for len(depths) > 0 && nextIndex < n { depth := depths[0] depths = depths[1:] for i := 0; i < 2; i++ { if nextIndex >= n { break } if arr[nextIndex] != "#" { childDepth := depth + 1 if childDepth > maxDepth { maxDepth = childDepth } depths = append(depths, childDepth) } nextIndex++ } } return maxDepth }

Python

from collections import deque def max_depth(arr): if not arr or arr[0] == '#': return 0 n = len(arr) next_index = 1 depths = deque([1]) max_depth_val = 1 while depths and next_index < n: depth = depths.popleft() for _ in range(2): if next_index >= n: break if arr[next_index] != '#': child_depth = depth + 1 max_depth_val = max(max_depth_val, child_depth) depths.append(child_depth) next_index += 1 return max_depth_val

C

#include <stdlib.h> typedef struct { int* data; int front, rear; int size; } Queue; Queue* createQueue(int n) { Queue* q = (Queue*)malloc(sizeof(Queue)); q->data = (int*)malloc(n * sizeof(int)); q->front = q->rear = -1; q->size = 0; return q; } void enqueue(Queue* q, int val) { q->data[++q->rear] = val; q->size++; } int dequeue(Queue* q) { q->size--; return q->data[++q->front]; } int max_depth(char** arr, int arrSize) { if (arrSize == 0 || strcmp(arr[0], "#") == 0) return 0; int next_index = 1; Queue* depths = createQueue(arrSize); enqueue(depths, 1); int max_depth_val = 1; while (depths->size > 0 && next_index < arrSize) { int depth = dequeue(depths); for (int i = 0; i < 2; i++) { if (next_index >= arrSize) break; if (strcmp(arr[next_index], "#") != 0) { int child_depth = depth + 1; if (child_depth > max_depth_val) max_depth_val = child_depth; enqueue(depths, child_depth); } next_index++; } } free(depths->data); free(depths); return max_depth_val; }

算法说明：