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

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

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

如果你不在底部，你可以向左或向右走。想象一下你向左走，看看距离底部还有多远。到左侧底部的距离就比该距离多一(计算 +1 向左的步数)。然后想象你向右走；到底部的距离又比从新位置向右移动一步测量时多了 1。如果向左表示向左走后还有 3 级台阶(算上向左初始台阶数为 4 级)，而向右走则表示到底部还有 6 级台阶(初始向右迈出的台阶为 7 级)，那么到底部的最长路径是 7(两者中较大的一个)。

       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(它们是递归的“终止条件”)。所有其他节点将检查两棵子树并查看哪一棵更深。