关于递归思路的详细个人见解(带图)

由来

这是一道在leetcode上的687题，由这个题我想谈一谈我对递归写法的个人见解。

题目描述

给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。 注意：两个节点之间的路径长度由它们之间的边数表示。 示例 1: 输入:

5 / \ 4 5 / \ \ 1 1 5

输出:

2

解题思路

我看了官方给的答案，但是官方给的答案说实话真的不好懂，给我的感觉就是奇淫巧技，没看懂这个递归函数的功能是什么。写递归程序，重要的是四点，输入参数、输出结果、函数的功能、终止条件。把这四点写明白，递归程序就写成了。其实递归本身就是完成一种功能的形式化描述。再往大点说，我们写的程序也是形式化描述，计算机又不懂你这背后的逻辑是什么，它只是按照指令的形式去执行而已，所以不需要费神去搞懂递归背后的逻辑。其实把递归函数的功能描述搞明白，就成功了一大半。

下面我们就来说说，这道题如何解决。 对于二叉树本身就具有递归这种性质的数据结构，我们需要把它看成“左子树-根节点-右子树”这种结构，就不要再囿于左子节点／右子节点这个思维里了。这道题其实可以看成是解决以root为路径起始点的最长路径，这其实就只有两种情况： (1)第一种是root和左子树（同值）； (2) 第二种是root和右子树（同值）。 但是还有种特殊情况，大家应该都能想到，就是左子树-root-右子树（同值），但是这种特殊情况不影响我们递归函数的功能设计。 下面我们先上代码。

解题代码

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { int ans; public int longestUnivaluePath(TreeNode root) { ans = 0; longestPath(root); return ans; } //递归函数功能：搜寻以node为起点的最长同值路径:要么是以node为起点的左子树，要么是以node为起点的右子树 public int longestPath(TreeNode node) { if (node == null) return 0; int maxLorRres=0; int left = longestPath(node.left); //node左子树的最长同值路径 int right = longestPath(node.right);//node右子树的最长同值路径 //这种情况对于寻找最长同值路径长有帮助，对于搜索以root为路径起始点的最长路径没有帮助 if (node.left != null && node.left.val == node.val&&node.right != null && node.right.val == node.val) { ans=Math.max(ans, left + right+2); } //从左右子树中选择最长的同值路径 if(node.left!=null&&node.left.val == node.val){ maxLorRres=left+1; } if(node.right!=null&&node.right.val==node.val){ maxLorRres=Math.max(maxLorRres,right+1); } //从ans与maxLorRres中更新最大值 ans=Math.max(ans,maxLorRres); return maxLorRres; //所以你能知道为什么返回这个值了吗？ } }

代码说明

我一直强调的是“其实递归本身就是完成一种功能的形式化描述”，那么我们的递归函数的功能是什么？看过代码后，应该知道了8。我们递**归函数的功能其实就是从左子树和右子树中返回一个最大的同值路径，**这也就是为什么我们return的是maxLorRres，即node左子树或右子树的最长同值路径。

很感谢这篇博客LeetCode 最长同值路径给了我灵感，不然看官答真的理解不了QAQ.