龙空技术网

「算法」求二叉树的最长同值路径

小亭聊技术 87

前言:

今天我们对“计算二叉树高度”大致比较珍视,各位老铁们都想要了解一些“计算二叉树高度”的相关知识。那么小编在网上收集了一些有关“计算二叉树高度””的相关知识,希望各位老铁们能喜欢,朋友们快快来了解一下吧!

给定一个二叉树,找到最长的路径,这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。

注意:两个节点之间的路径长度由它们之间的边数表示。

示例 1:

输入:

输出:

2

示例 2:

输入:

输出:

2

注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。

解题方案:

采用递归的方法解决该问题。

思路

我们可以将任何路径(具有相同值的节点)看作是最多两个从其根延伸出的箭头。

具体地说,路径的根将是唯一节点,因此该节点的父节点不会出现在该路径中,而箭头将是根在该路径中只有一个子节点的路径。

然后,对于每个节点,我们想知道向左延伸的最长箭头和向右延伸的最长箭头是什么?我们可以用递归来解决这个问题。

算法

令 pathLength(node) 为从节点 node 延伸出的最长箭头的长度。如果 node.Left 存在且与节点 node 具有相同的值,则该值就会是 1 + pathLength(node.left)。在 node.right 存在的情况下也是一样。

当我们计算箭头长度时,候选答案将是该节点在两个方向上的箭头之和。我们将这些候选答案记录下来,并返回最佳答案。

int ans = 0;public int longestUnivaluePath(TreeNode root) {    pathLength(root);    return ans;}private int pathLength(TreeNode node) {    if (node == null) return 0;    int left = pathLength(node.left);    int right = pathLength(node.right);    int leftValue = (null != node.left && node.val == node.left.val) ? left + 1 : 0;    int rightValue = (null != node.right && node.val == node.right.val) ? right + 1 : 0;    ans = Math.max(ans, leftValue + rightValue);    return Math.max(leftValue, rightValue);}

标签: #计算二叉树高度