在C++中遍历二进制树中的每条路径的逻辑是什么

Question

这是我第一次研究二叉树，我看到了很多关于路径遍历的问题，其中一个问题是找到特定节点的路径。这在二进制搜索树中很容易，但在普通的二进制树中很难，因为节点中的元素之间没有关系。我提出了许多逻辑，但没有一个适用于树中的所有节点。我也想知道遍历从根到叶节点的每条路径的逻辑是什么。

谢谢。

Answer 1

使用递归。具体的细节取决于你如何定义你的树，但它可能看起来像这个

void visit(TreeNode* node, vector<Node*>& path)
{
    // check for NULL
    if (node == NULL)
        return;
    // add node to path
    path.push_back(node);
    // print the node path
    ...
    // visit left child
    visit(node->left, path);
    // visit right child
    visit(node->right, path);
    // remove node from path
    path.pop_back();
}
// start at the root
vector<Node*> path;
visit(root, path);