递归在这个二叉树最长路径函数中是如何工作的？

Question

我现在正在做一项作业，我已经在网上找到了解决问题的方法（看起来简单得离谱，但就像魔术一样）

我仍然很难理解递归到底是如何工作的，我真的很想学。

有人能帮我理解这个逻辑吗？

问题是找到从根节点到叶节点的最长路径。（基本上找到树的高度？）。

函数如下：

public static int findPath(TreeNode<Integer> node)
    {
        if (node == null)
            return 0;
        else
        {
            return 1 + Math.max(findPath(node.left), findPath(node.right) );
        }
    }

这是我的treeNode类定义：

public class TreeNode<T> {
    T v;
    TreeNode<T> left;
    TreeNode<T> right;
    TreeNode(T value) //initialize treeNode with treeNode(value) 
    {
        v = value;
        left = null;
        right = null;
    }
}

Answer 1

如果它能帮助你：

首先，将＜code＞findPath＜/code＞重命名为更合适的名称，如＜code＞longestPathLength＜/code>。

然后您可以将1视为因式分解，但它仍然可以是非因式分解：

Math.max(1 + findPath(node.left), 1 + findPath(node.right) );

这个想法是：在从根到尽头的所有路径中，一些穿过左边的子树，另一些穿过右边的子树。

通过左子树的最长路径长度为：左子树中最长路径的长度，加上外部根节点的长度。我在右边。

但是最终递归是你必须要解决的问题。首先在一些简单的数学例子或者更简单的数据结构(比如一个列表的长度)上看到它会有所帮助。

Answer 2

如果你在底部，到底部的最大路径是零。

如果你不在底部，你可以向左或向右走。想象你向左走，看看它到底有多远。到左侧底部的距离则比该距离大一（计算1的左侧步数）。然后想象你走对了；到底部的距离又比你从新位置向右一步测量的距离多一倍。如果向左走表示在向左走之后还有三步（四步算上最初的向左步），向右走表示还有六步到达底部（七步算上第一步的向右步），那么到达底部的最长路径是七步（二者中的较大者）。

       A
      / \
     /   \
    B     C
   / \   ' `
  D   E
 ' ` ' \
        F
       ' `

说这是我们的树。从A向左走，还有3步要走；向右走还有1步。因此，来自A的总最大路径长度为4（＜code＞1 max（3，1）＜/code＞）。

我们怎么知道B有3步？嗯，向左走，从底部开始有1步。向右走，还有2步。1 max（1,2）是3。

等等，我们怎么知道从D到还有一步？这就是方法：向左走，我们在底部（那里什么都没有），所以距离是 0。向右走，同样的事情：再次0。1 最大值（0， 0） 为 1。

所有其他节点的计算类似。所有显示为中止弧的节点的值都为0（它们是递归的“终止条件”）。所有其他节点都将检查两个子树，看看哪一个子树更深。