二叉树递归 java

Question

我想编写一个函数，其中 return 是一个由 0 和 1 组成的字符串，表示从根节点到特定节点 p 的路径，其中 0 表示向左走，1 表示向右走。

2 应该 return "01"

public String traverse(TreeNode root, TreeNode p,String s) {
    if (root == p) return s;
    if (root.left != null) return traverse(root.left,p,s + "0");

    if (root.right != null) return traverse(root.right,p,s+ "1"); 

    return "-1";
  }

这是我对递归方式的想法，但是当它到达叶子时它只是 returns -1，而我希望它继续递归。比如，要找到 2，它会尝试 3 -> 4-> 9，但不会继续 4 的递归，而是在 9 处停止。我该怎么办？

Answer 1

您将返回一个特殊的 sentinel 值，当您在树的特定分支上找不到您要查找的值时为“-1”。

但是您没有在代码中的任何位置检查此值 - 当您要查找的值不在树的左分支上时，您需要在右分支中搜索。

因此，您需要在搜索树的左分支后添加一个检查，以确保您没有得到哨兵值作为结果。如果是，则需要继续搜索。

public String traverse(TreeNode root, TreeNode p, String s) {
    if (root == p) {
        return s;
    }
    if (root.left != null) {
        String result = traverse(root.left, p, s + "0");
        if (!"-1".equals(result)) {
            return result;
        }
    }
    if (root.right != null) {
        return traverse(root.right, p, s + "1");
    }
    return "-1";
}

二叉树递归 java

Binary tree recursion java

java

string

recursion

binary-tree