使用递归在二叉树中根和节点之间的距离

Question

我读了一个算法来查找二叉树中两个节点之间的距离。在从根到节点的距离中，需要给定节点的最低共同祖先。
这段代码在二叉树中查找（1 + 从根到给定节点的距离）。

 int Pathlength(Node* root, int n1) {
        if (root != NULL) {
            int x=0;
            if ((root->data == n1) || (x=Pathlength(root->left, n1))>0||(x=Pathlength(root->right, n1))>0) 
            {

                return x + 1;
            }
            return 0;
        }
     return 0;
    }

我不明白的是'x'有两个值，一个来自左子树，另一个来自右子树，它怎么知道哪个值到return？
例如，如果树是这样的：

20  
/  \  
8  2

然后调用 Pathlength(root, 8)、

x=Pathlength(root->left,8)=1  
x=Pathlength(root->right,2)=0

那么，在语句“return x+1”中，它如何return得到正确的 x 值？

Answer 1

你要明白在C/C++中，逻辑或||是短路：

计算 A || B 时，如果 A 为真，则不计算 B（因为无论 B 是什么，A||B 始终为真）。

在此表达式中：

(root->data == n1) || (x=Pathlength(root->left, n1))>0||(x=Pathlength(root->right, n1))>0

由于Pathlength(root->left, n1)为1，赋值给x，x>0求值为True，不再调用x=Pathlength(root->right, n1)。

使用递归在二叉树中根和节点之间的距离

Distance between root and node in binary tree using recursion

algorithm

recursion

binary-tree

dynamic-programming