求二叉树的广度和深度
1、常见二叉树数据结构如下：
| 1 2 3 4 5 6 7 8 9 10 | /* * Definition for a binary tree node. */ struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; |
2、二叉树的深度
可以使用递归算法分别求出左子树和右子树的深度，两个深度的较大值 +1 即可。代码如下：
| 1 2 3 4 5 6 7 8 9 | public static int getMaxDepth(TreeNode root) { if (root == null) return 0; else { int left = getMaxDepth(root.left); int right = getMaxDepth(root.right); return 1 + Math.max(left, right); } } |
3、二叉树广度
求二叉树的广度需要使用队列，层次遍历二叉树。在上一层遍历完成后，下一层的所有节点已经放到队列中，此时队列中的元素个数就是下一层的宽度。以此类推，依次遍历下一层即可求出二叉树的最大宽度。代码如下：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | public static int getMaxWidth(TreeNode root) { if (root == null) return 0; Queue<TreeNode> queue = new ArrayDeque<TreeNode>(); int maxWitdth = 1; // 最大宽度 queue.add(root); // 入队 while (true) { int len = queue.size(); // 当前层的节点个数 if (len == 0) break; while (len > 0) { // 如果当前层，还有节点 TreeNode t = queue.poll(); len--; if (t.left != null) queue.add(t.left); // 下一层节点入队 if (t.right != null) queue.add(t.right);// 下一层节点入队 } maxWitdth = Math.max(maxWitdth, queue.size()); } return maxWitdth; } |
查看9道真题和解析