687.最长同值路径
一、题目概述
给定一个二叉树,找到最长的路径,这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意:两个节点之间的路径长度由它们之间的边数表示。
示例 1:
输入:
5
/ \
4 5
/ \ \
1 1 5
输出:
2
示例 2:
输入:
1
/ \
4 5
/ \ \
4 4 5
输出:
2
注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。
二、解题方案
思路:采用递归的方法
- 将该二叉树的每个节点都当作根节点;
- 专门写一个递归函数(arrowLength),参数为节点指针,返回值为子节点最大的同值路径
- 声明一个全局变量(ans),在递归函数中与结点指针对应的同值路径比较,更新ans
- 递归函数首先依次递归二叉树的所有节点,遇到叶子节点则返回0,如果遇到非叶子节点,比较左右子节点,若存在左、右子节点且值等于根节点值,则同值路径+1,左右同值路径之和与ans相加取其较大的值,返回左右同值路径中较大的值。
int ans;
int longestUnivaluePath(TreeNode* root) {
ans = 0;
if (root == NULL) return 0;//若为空树则直接返回0
arrowLength(root);
return ans;
}
int arrowLength(TreeNode* root) {
//递归到叶子节点 则返回 0
if (root == NULL) return 0;
int left = 0, right = 0;
//递归左右子节点 返回路径数
int leftArrow = arrowLength(root->left);
int rightArrow = arrowLength(root->right);
//若子节点存在且与根节点相等
if (root->left != NULL && root->val == root->left->val) {
left = leftArrow + 1;
}
if (root->right != NULL && root->val == root->right->val) {
right = rightArrow + 1;
}
ans = ans > (left + right) ? ans : (left + right);
return left > right ? left : right;
}