c++用栈求二叉树节点距离

在C++中，我们可以使用栈（Stack）来解决二叉树节点之间的最短路径问题，例如找到任意两个节点间的最小步长（假设每次只能向上或向下移动一步）。这通常涉及到层次遍历（Level Order Traversal），特别是广度优先搜索（BFS）。

首先，我们需要维护一个队列（可以视为先进先出的数据结构，类似栈）来存储每层的节点。然后，对于给定的目标节点，我们可以在遍历时记录当前节点到根节点的距离，并更新其子节点的距离。如果目标节点也在队列中，那么它们之间的距离就是两者距离的差值，因为这意味着不需要额外上下移动就能到达。

下面是一个简单的伪代码概述：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
};

// 定义一个辅助结构，包含节点和它的深度
struct NodeWithDepth {
    TreeNode* node;
    int depth;
};

void findDistance(TreeNode* root, TreeNode* target1, TreeNode* target2) {
    queue<NodeWithDepth> q {{root, 0}};
    unordered_map<TreeNode*, int> distance; // 存储每个节点到根节点的距离
    distance[root] = 0;

    while (!q.empty()) {
        NodeWithDepth nwd = q.front();
        q.pop();

        if (distance.find(nwd.node->left) == distance.end()) {
            distance[nwd.node->left] = nwd.depth + 1;
            q.push({nwd.node->left, nwd.depth + 1});
        }
        if (distance.find(nwd.node->right) == distance.end()) {
            distance[nwd.node->right] = nwd.depth + 1;
            q.push({nwd.node->right, nwd.depth + 1});
        }

        if (nwd.node == target1 || nwd.node == target2) {
            // 如果找到目标节点之一，检查另一个是否在队列中
            if (distance.find(target2) != distance.end()) {
                cout << "距离: " << abs(distance[target1] - distance[target2]) << endl;
            } else {
                q.push({target2, distance[target1]});
            }
        }
    }
}

注意，这个算法假设二叉树是非空的，并且每个节点都有左右孩子。如果没有找到目标2，它会尝试将目标2加入队列，以便后续查找。