基于递归的二叉树根节点距离

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”有两个值，一个来自左子树，另一个来自右子树，它如何知道返回哪个值
例如，如果树类似于：

20  
/  \  
8  2

然后调用路径长度（根，8），

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

那么，在语句“returnx1”中，它如何返回正确的x值？

Answer 1

你需要明白在C/C中，逻辑OR||是短路的：

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

在此表达式中：

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

自路径长度（根）-