二叉树最大通路长度：递归与迭代解法

“一棵二叉树，求最大通路长度（即最大左右子树高度之和）” 这道问题涉及到二叉树数据结构及其遍历，主要目标是找到一棵二叉树的最大通路长度，这里的通路长度指的是左右子树的高度之和。在二叉树中，节点的高度是指从该节点到其最远叶子节点的边的数目。给定一个二叉树的根节点，我们需要计算整个树中的最大通路长度。 首先，我们可以看到提供了两种解题方法，分别是递归和迭代。 解法一：递归求解 递归方法基于二叉树的分治思想，将问题分解为更小的子问题。在这个解法中，我们首先判断根节点是否为空，如果为空则返回0表示没有高度。然后，我们分别计算左子树和右子树的最大高度，取两者中的较大值，并加1（因为根节点本身占了一层高度）。最后，返回左右子树最大高度之和作为当前节点的最大通路长度。 ```java class Solution { public int maxHeight(TreeNode root) { if (root == null) { return 0; } return maxChildHeight(root.left) + maxChildHeight(root.right); } public int maxChildHeight(TreeNode root) { if (root == null) { return 0; } int leftHeight = maxChildHeight(root.left); int rightHeight = maxChildHeight(root.right); return Math.max(leftHeight, rightHeight) + 1; } } ``` 解法二：迭代求解 迭代方法使用了广度优先搜索（BFS）策略。从根节点开始，将所有节点按层级放入队列中。每轮循环，我们处理队列中的所有节点，更新高度并将其非空子节点加入队列。当队列为空时，表示已遍历完所有节点，此时的高度就是最大通路长度。 ```java public class Solution { public int maxHeight(TreeNode root) { if (root == null) { return 0; } return maxChildHeight(root.left) + maxChildHeight(root.right); } public int maxChildHeight(TreeNode root) { int height = 0; Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); height++; if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } } return height; } } ``` 在这两个解法中，递归方法更适合于理解问题的本质，但可能会遇到栈溢出的问题，尤其是对于深度较大的二叉树。而迭代方法虽然代码稍显复杂，但可以避免递归带来的栈空间问题，适合处理大规模数据。在实际应用中，可以根据具体情况选择合适的解法。