前言:
今天我们对“计算二叉树高度”大致比较珍视,各位老铁们都想要了解一些“计算二叉树高度”的相关知识。那么小编在网上收集了一些有关“计算二叉树高度””的相关知识,希望各位老铁们能喜欢,朋友们快快来了解一下吧!给定一个二叉树,找到最长的路径,这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意:两个节点之间的路径长度由它们之间的边数表示。
示例 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);}
标签: #计算二叉树高度