LeetCode 例题精讲 | 10 二叉树直径：二叉树遍历中的全局变量

本期例题：二叉树的直径

LeetCode 543 - Diameter of Binary Tree^[1]（Easy）

给定一棵二叉树，计算它的直径。二叉树的直径是任意两个结点之间的路径长度中的最大值。这条路径有可能不经过根结点。

二叉树的直径这道题是一道非常经典的面试题。我曾经在面试遇到过原题，也听周围参加面试的小伙伴提起过好几次。同时，这道题也是一道非常有代表性的题目，可以用来理解一类带有全局变量的二叉树遍历。本文就来详细讲解这个题目中的道理。

这篇文章将会包含：

• 二叉树直径问题的子问题解法
• 二叉树直径问题的全局变量解法
• 一类全局变量问题的规律
• 相关题目

二叉树直径问题的思路

我们在第二讲中讲过了二叉树的子问题划分（点击这里回顾第二讲内容）。二叉树的解题技巧是，首先判断问题能否划分为子问题、应当划分为什么样的子问题。对于二叉树直径（最长路径）问题，需要明确的一点是，二叉树中的最长路径不一定经过根结点：

二叉树中的最长路径不一定经过根结点

这给我们的子问题划分带来了一点难度。但是稍加思考，还是可以划分出子问题的：

子问题之左右子树的最长路径

其中左子树的最长路径和右子树的最长路径是两个可以递归求解的子问题，那么经过根结点的最长路径如何计算呢？是左子树的深度加上右子树的深度。

根据左右子树的深度计算出最长路径

代入上面的式子得到：

等等。这里好像出现了两个子问题：子树的最大直径、子树的最大深度。这难道是要让我们把树遍历两遍吗？非也，我们只需要让遍历函数返回两个值即可。

语言小贴士： 在不同的语言中，该怎么让函数返回多个值？

在 C++ 中，如果返回两个值，使用 std::pair；如果返回多个值，使用 std::tuple。

// 函数返回
pair<char, int> foo() {
	return make_pair('a', 314);
}
// 函数调用
auto pair = foo();
char a = pair.first;
int b = pair.second;

在 Java 中，如果返回的值类型相同，使用数组。如果返回的值类型不同，需要自己现写一个类。

// 函数返回
int[] foo() {
    return new int[]{314, 315};
}
// 函数调用
int[] res = foo();
int a = res[0];
int b = res[1];

在 Python 中，有 tuple 类型以及 auto-unpacking，函数返回多个值非常自然。

# 函数返回
def foo():
    return ('a', 314)
# 函数调用
a, b = foo()

让我们用函数返回多个值比较方便的 Python 来写示例代码。我们让遍历函数返回二元 tuple，第一个值是子树的最大深度，第二个值是子树的最长路径（直径）。

# return (depth, diameter)
def traverse(root):
    if root is None:
        return (0, 0)

    left_depth, left_diam = traverse(root.left)
    right_depth, right_diam = traverse(root.right)
    # 求二叉树深度的常规方法
    depth = 1 + max(left_depth, right_depth)
    # 套用上面推导出的最长路径公式
    diam = max(left_diam, right_diam, left_depth + right_depth)
    return depth, diam

def diameterOfBinaryTree(root):
    depth, diam = traverse(root)
    return diam

这道题用 Python 写起来倒是方便了。但是用 C++ 和 Java 呢？简直麻烦得要死。接下来，我们看看这道题有没有更好的方法。

二叉树遍历中的全局变量

乍一看来，我们的遍历函数必须返回两个值。如果我们把返回两个值的函数拆成两个函数，会出现重复递归，拖慢算法的执行时间。但仔细一看代码，似乎发现了点什么：

如果我们看函数返回的第二个值，也就是子树的直径（最长路径），我们会发现，我们所做的，不过是递归计算左右子树的最长路径，然后再通过这个计算出当前树的最长路径。既然我们始终都是在求它的最大值，那么用一个全局变量保存它的最大值不就可以了？

Amazing！也就是说，我们把最大直径放在函数返回值里，是让其中的某个最大值一层一层地返回上去，直到 DFS 的起点。而使用全局变量的话，则是让最大值可以直接抵达终点。

这样，我们的函数就可以只返回一个变量了。以下是 Java 版题解代码：

int diameter;

public int diameterOfBinaryTree(TreeNode root) {
    diameter = 0;
    traverse(root);
    return diameter;
}

// 返回树的深度
int traverse(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int left = traverse(root.left); // 左子树的深度
    int right = traverse(root.right); // 右子树的深度
    // 直接访问全局变量
    diameter = Math.max(diameter, left + right);
    return 1 + Math.max(left, right);
}

相似题目：二叉树最大路径和

我们再来看一道非常相似的题目加深理解：

LeetCode 124 - Binary Tree Maximum Path Sum^[2]（二叉树的最大路径和，Hard）

给定一棵二叉树，计算它的最大路径和。每条路径应至少包含一个结点。这条路径可能不经过根结点。注意：二叉树中的结点可能有负数值。

这道题和二叉树直径题目非常相似。只不过二叉树直径问题求的是最长路径，这道题求的是和最大的路径。我们可以定义根路径是指从根结点出发的路径。这样，这道题的子问题可以划分为：

以下是题目的题解代码，同样是遍历函数返回一个值，并使用一个全局变量，与二叉树直径的代码相似度 90%。

int res;

public int maxPathSum(TreeNode root) {
    res = Integer.MIN_VALUE;
    traverse(root);
    return res;
}

// return max root path sum
int traverse(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int left = traverse(root.left);
    int right = traverse(root.right);
    int maxPathSum = root.val + Math.max(0, left) + Math.max(0, right);
    res = Math.max(res, maxPathSum);
    return root.val + Math.max(0, Math.max(left, right));
}

不过这道题的一个难点在于，由于负数值的影响，在计算最大和路径的时候要及时舍去和为负的路径。不过这和本文的主题不甚相关，读者可以自行练习揣摩。

全局变量方法的更多应用

那么，这样一个使用全局变量遍历二叉树的方法，除了求最最大值，还能用来计算其他的吗？答案是可以的，这里举两道题作为例子。

全局变量方法应用于 max 以外的操作

LeetCode 110 - Balanced Binary Tree^[3]（判断平衡二叉树）（Easy）

给定一个二叉树，判断它是否为平衡二叉树。

在平衡二叉树中，任意结点的左右子树的高度相差不超过 1。

在这道题中，“是否为平衡二叉树”可以定义为全局变量，初始值为 true。遍历到一个结点的时候，如果发现它左右子树的高度不平衡，就让全局变量变为 false。

boolean balanced;

public boolean isBalanced(TreeNode root) {
    balanced = true;
    traverse(root);
    return balanced;
}

// 返回树的高度
int traverse(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int left = traverse(root.left);
    int right = traverse(root.right);
    // 判断当前子树是否平衡，修改全局变量
    if (Math.abs(left - right) > 1) {
        balanced = false;
    }
    return 1 + Math.max(left, right);
}

LeetCode 563 - Binary Tree Tilt^[4]（二叉树的坡度，Easy）

给定一个二叉树，计算整个树的坡度。

树中结点的坡度定义为：该结点左子树的结点值之和和右子树结点值之和的差的绝对值。空结点的的坡度是 0。整棵树的坡度就是其所有结点的坡度之和。

在这道题中，整棵树的坡度可以定义为全局变量。遍历到一个子树的时候，将子树的坡度累加到全局变量上。

int tilt;

public int findTilt(TreeNode root) {
    tilt = 0;
    traverse(root);
    return tilt;
}

// 返回：结点值之和
int traverse(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int left = traverse(root.left);
    int right = traverse(root.right);
    // 计算当前子树的坡度，累加到全局变量
    tilt += Math.abs(left - right);
    return root.val + left + right;
}

全局变量方法的原理：在线算法

我们注意观察三道例题中全局变量计算的值：

• 二叉树直径问题，全局变量计算的是最大值（max）；
• 二叉树坡度问题，全局变量计算的是和（sum）；
• 平衡二叉树问题，全局变量计算的是 all，即 x1 && x2 && ... && xn。

只不过这些 max、sum、all 操作不是一次性求出来的，而是在二叉树遍历的过程中，每出现一个值，就把这个值和全局变量进行计算。最终全局变量就是最终的结果。这种计算过程有一个术语，叫做在线算法（online algorithm）^[5]。

在线算法，简单来说，就是所有的输入数据以“流”的形式一个个进来，算法每次只处理一个（或一小块）数据，不需要保存全部的数据。上面的 max、sum、all 这几个都属于在线算法。也有很多操作不是在线算法，称为离线算法，典型的一个例子是标准差 stddev。

对于使用全局变量的二叉树遍历来说，每次是出来一个值和全局变量计算一下，这些值不会全部保存下来。因此，这个全局变量所对应的操作应当是一个在线算法。幸运的是，max、sum、all 这些操作全都是在线算法。

总结

本文讲解了二叉树遍历中使用全局变量的技巧。必须要注意的一点是：全局变量只是让代码更简洁的一个技巧。实际上完全不使用全局变量，像文本一开始讲的那样，让递归函数返回两个值，也是完全可行的。在我们思考一道二叉树题目的时候，应该首先用标准的子问题分析法确定二叉树遍历中的子问题，再伺机用全局变量进行优化。

更多在二叉树遍历中使用全局变量的相关题目：

• LeetCode 129 - Sum Root to Leaf Numbers^[6]（Medium）
• LeetCode 1372 - Longest ZigZag Path in a Binary Tree^[7]（Medium）
• LeetCode 1373 - Maximum Sum BST in Binary Tree^[8]（Hard）

往期文章

参考资料

[1]

LeetCode 543 - Diameter of Binary Tree: https://leetcode.com/problems/diameter-of-binary-tree/

[2]

LeetCode 124 - Binary Tree Maximum Path Sum: https://leetcode.com/problems/binary-tree-maximum-path-sum/

[3]

LeetCode 110 - Balanced Binary Tree: https://leetcode.com/problems/balanced-binary-tree/

[4]

LeetCode 563 - Binary Tree Tilt: https://leetcode.com/problems/binary-tree-tilt/

[5]

在线算法（online algorithm）: https://en.wikipedia.org/wiki/Online_algorithm

[6]

LeetCode 129 - Sum Root to Leaf Numbers: https://leetcode.com/problems/sum-root-to-leaf-numbers/

[7]

LeetCode 1372 - Longest ZigZag Path in a Binary Tree: https://leetcode.com/problems/longest-zigzag-path-in-a-binary-tree/

[8]

LeetCode 1373 - Maximum Sum BST in Binary Tree: https://leetcode.com/problems/maximum-sum-bst-in-binary-tree/