递归实现二叉树第k个祖先函数出错，请求排查修正

问题描述 #

给定一棵大小为N的二叉树、一个node节点和正整数k，需完成函数kthAncestor()，返回该节点的第k个祖先，若不存在则返回-1。
注意： 保证node节点存在于树中。

约束条件： #

• 1 <= N <= 10^4
• 1 <= K <= 100

我的代码 #

class Tree
{
    public Node solve(Node root,int k,int node)
    {
        if(root==null)
            return null;
        if(root.data==node)
            return root;
        Node l=solve(root.left,k,node);
        Node r=solve(root.right,k,node);
        if(l!=null && r==null)
        {
            k--;
            if(k==0)
                return root;
            return l;
        }
        else if(r!=null && l==null)
        {
            k--;
            if(k==0)
                 return root;
            return r;
        }
        else
            return null;
    }
    public int kthAncestor(Node root, int k, int node)
    {
        //Write your code here
        if(root.data==node && k==0)
            return node;
        if(root.data==node && k>0)
            return -1;
        Node ans=solve(root,k,node);
        if(ans==null)
            return -1;
        else
            return ans.data;
    }
}

错误测试用例 #

• 输入：

  K = 2
  Node = 4
  

• 预期输出：1
• 实际输出：4

问题原因与修正 #

核心问题是**k按值传递**，递归中修改的k无法影响上层递归的变量。比如找到目标节点后，每回溯一层尝试减k，但这个修改仅在当前函数栈有效，上层的k仍为初始值，最终返回目标节点本身而非第k个祖先。

修正方案1：用数组实现引用传递 #

class Tree
{
    private void solve(Node root, int[] k, int node, Node[] result) {
        if (root == null || result[0] != null) {
            return;
        }
        if (root.data == node) {
            return;
        }
        solve(root.left, k, node, result);
        solve(root.right, k, node, result);
        
        if (result[0] == null && (root.left != null && root.left.data == node || root.right != null && root.right.data == node)) {
            k[0]--;
            if (k[0] == 0) {
                result[0] = root;
                return;
            }
            node = root.data;
        }
    }
    
    public int kthAncestor(Node root, int k, int node) {
        if (root.data == node) {
            return k == 0 ? node : -1;
        }
        Node[] result = new Node[1];
        solve(root, new int[]{k}, node, result);
        return result[0] == null ? -1 : result[0].data;
    }
}

修正方案2：记录路径直接取值（逻辑更直观） #

import java.util.ArrayList;
import java.util.List;

class Tree
{
    private boolean getPath(Node root, int node, List<Integer> path) {
        if (root == null) {
            return false;
        }
        path.add(root.data);
        if (root.data == node) {
            return true;
        }
        if (getPath(root.left, node, path) || getPath(root.right, node, path)) {
            return true;
        }
        path.remove(path.size() - 1);
        return false;
    }
    
    public int kthAncestor(Node root, int k, int node) {
        List<Integer> path = new ArrayList<>();
        getPath(root, node, path);
        if (path.size() <= k) {
            return -1;
        }
        return path.get(path.size() - k - 1);
    }
}

内容的提问来源于stack exchange，提问作者Akash Mahato