algorithm - 通过添加或乘以节点找到树可以生成的所有数字

Question

我想从二叉搜索树的根部找到一条路径，是否可以通过添加或乘以节点来生成特定的数字。

换句话说，我想显示所有数字，这些数字可以通过在路径的节点之间添加 * 或 + 来生成。

注意路径应该从根到叶。

例如:

tree nodes: 10, 8, 3

number can produce from this path:

240 => 10 * 8 * 3

110 => 10 * (8 + 3)

21 => 10 + 8 + 3

83 => (10 * 8) + 3

54 => (10 + 8) * 3

34 => 10 + (8 * 3)

这段代码是我写的，没有括号。

 private void findThePath(TreeNode tnode, int result, int n, List paths) {
        // if node is null, return
        if (tnode == null)
            return;


    //adding nodes to this list, in order to save the path
    paths.add(tnode);

    // if node is leaf node, and its data equals
    // to user input, its path highlighted
    if (tnode.leftCircle == null && tnode.rightCircle == null) {
        if (result == n) {
            paths.forEach(t -> t.highlightFlag = true);
            paths.forEach(t -> System.out.print(t.rootCircle.getSearchKey() + " "));
        }
    }

    // if left child exists, check for leaf,
    // and insert * or + sign between nodes,
    // recursively
    if (tnode.leftCircle != null) {
        findThePath(tnode.leftCircle, result + tnode.leftCircle.rootCircle.getSearchKey(), n, paths);
        findThePath(tnode.leftCircle, result * tnode.leftCircle.rootCircle.getSearchKey(), n, paths);
    }

    // if right child exists, check for leaf
    // and insert * or + sign between nodes,
    // recursively
    if (tnode.rightCircle != null) {
        findThePath(tnode.rightCircle, result + tnode.rightCircle.rootCircle.getSearchKey(), n, paths);
        findThePath(tnode.rightCircle, result * tnode.rightCircle.rootCircle.getSearchKey(), n, paths);
    }

    //we need to remove the last node in list because
    //its not in left or right of the nodes
    paths.remove(paths.size() - 1);
}

see the output here:

它不包含 8 * (5 + 3) 和 8 + (5 * 3)。

Answer 1

如果为三个节点生成的数字，则递归遍历树并在每个节点检查它是否同时具有可以运行给定方程的左右节点，如果它给出数字，则打印节点。