递归如何在此二叉树最长路径函数中工作？

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 class 定义：

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

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

如果你不在底部，你可以向左或向右走。想象一下你向左走，看看离底部还有多远。到左边底部的距离比那个多一（计算 +1 左边的步数）。然后想象你向右走；到底部那里的距离再次比从新位置向右一步测量时多一倍。如果向左走表示向左走后还有三步（四步算左初始步），向右走表示还有六步到底部（七步向右初始步），那么到底部的最长路径是七（两者中较大者）。

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

说这是我们的树。从A开始，向左走，还有3步；向右走还有 1 个。因此，A 的总最大路径长度为 4 (1 + max(3, 1))。

我们怎么知道 B 有 3 个步骤？嗯，向左走，从底部开始有 1 步。向右走，还有 2 个步骤要走。 1 + max(1, 2) 是 3。

等等，我们怎么知道从 D 走了一步？这是这样的：向左走，我们在底部（那里什么都没有），所以距离为 0。向右走，同样的事情：再次为 0。 1 + max(0, 0) 是 1。

所有其他节点的计算类似。所有显示为中止弧的节点的计算结果为 0（它们是递归的 "terminating condition"）。所有其他节点将检查两个子树并查看哪个更深。

Answer 2

如果对您有帮助：

首先，将 findPath 重命名为更合适的名称，例如 longestPathLength。

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

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

思路是：从根到终点的所有路径中，有的通过左子树，有的通过右子树。

最长路径通过左子树的长度为：最长路径在左子树的长度-tree，加上一个用于外部的根节点。右侧同上。

但最终递归是你必须理解的东西。它可以帮助首先在一些简单的数学示例或更简单的数据结构（如列表长度）上看到它。

递归如何在此二叉树最长路径函数中工作？

How does recursion work in this binary tree longest path function?

java

tree

recursion

binary-tree