二叉树节点递归查找的更优实现方式咨询

嘿各位，我刚完成作业里的二叉树节点查找功能，写了一段递归代码，但总觉得绕了弯路，想请教下有没有更简洁的递归实现方式。

先贴我最初写的代码：

typedef struct NODE {
    int key;
    struct NODE *left, *right;
} Node;

Node *search(Node *head, int key) {
    if (!head) return 0;
    if (head->key == key) return head;
    return or(search(head->left, key), search(head->right, key));
}

Node *or(void *ptr1, void *ptr2) {
    Node *temp = (Node *)((long)ptr1 | (long)ptr2);
    return temp;
}

我的思路是递归遍历左右子树，没找到返回NULL，找到就返回节点地址。当时脑抽搞了个按位或操作指针，想着这样只要任意一边找到节点，就能返回非零地址。代码能跑，但这指针操作完全是画蛇添足，感觉复杂过头了。

（编辑补充：后来我突然反应过来，其实完全不用搞这些花里胡哨的，直接这么写就行：

Node *left = search(head->left,key) ;
if(left) return left ;
else return search(head->right,key) ;

）

哈哈，你最后补充的这段代码就是最标准、最清爽的递归实现啦！

不得不说，你一开始用按位或操作指针的思路虽然能工作，但真的没必要——指针的位操作不仅可读性极差，还可能在一些特殊架构下（比如指针宽度和long不匹配的情况）埋下兼容性隐患，属于完全没必要的“炫技”操作。

标准的二叉树递归查找逻辑其实非常直白：

1. 先判断当前节点是否为空，是空就直接返回NULL
2. 如果当前节点的key正好匹配，直接返回当前节点
3. 先递归查找左子树，如果左子树返回了非空指针（说明找到节点了），直接把这个结果返回
4. 要是左子树没找到，再递归查找右子树，返回右子树的查找结果

把这个逻辑整理成完整的函数就是：

Node *search(Node *head, int key) {
    if (!head) {
        return NULL;
    }
    if (head->key == key) {
        return head;
    }
    Node *left_result = search(head->left, key);
    if (left_result) {
        return left_result;
    }
    return search(head->right, key);
}

这种写法逻辑清晰，一眼就能看懂，完全没有多余的复杂操作，就是递归查找二叉树节点的常规操作～

内容来源于stack exchange