6. 树中查找节点

来源：百度二面

题目

给定一个树形结构数据，根据 id 查找并返回对应节点。

代码

// 给一个树形结构的数据，要求根据id找到数据
// 百度二面

function findTreeNode(tree, id) {
    for(const node of tree) {
        if (node.id === id) {
            return node;
        }

        if(node.children){
            const res = findTreeNode(node.children, id);
            if(res) return res;
        }
    }
    return null;
}

function findTreeNode2(head, id) {
    if(!head) return null
    if(head.id === id) return head;
    return findTreeNode2(head.left, id) || findTreeNode2(head.right, id);
}

思路

方法一：通用树递归查找

对于多叉树，可以从当前层开始遍历：

1. 依次检查当前节点的 id 是否等于目标值
2. 如果命中，直接返回当前节点
3. 如果当前节点存在 children，就在子树中继续递归查找
4. 只要某个子树返回结果，立刻向上返回

方法二：二叉树递归查找

如果题目给的是标准二叉树结构，也可以直接递归左右子树：

1. 空节点直接返回 null
2. 当前节点命中就返回当前节点
3. 否则继续在左子树、右子树中查找
4. 利用逻辑或返回第一个非空结果

关键点

• 本质是 DFS 深度优先搜索
• 找到目标后应立即返回，避免无效遍历
• 通用树通常遍历 children，二叉树则递归 left / right
• 时间复杂度最坏为 $O(n)$，空间复杂度为递归深度 $O(h)$