非递归:
#include <iostream>
#include <stack>using namespace std;// 二叉树结点定义
struct TreeNode
{int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};// 非递归后序遍历查找路径m->n
void postorder(TreeNode* root, TreeNode* n)
{stack<TreeNode*> stk;TreeNode* cur = root;TreeNode* prev = NULL;while(cur || !stk.empty()){// 将当前节点及其左节点全部入栈while(cur){stk.push(cur);cur = cur->left;}cur = stk.top();// 如果栈顶没有右子节点或右子节点已经访问完if(!cur->right || cur->right == prev){if (cur->val == n->val) // 访问到目标结点n时{while(!stk.empty()) // 输出栈中元素{cout << stk.top()->val << ' ';stk.pop();}return ;}stk.pop();prev = cur;cur = nullptr;}else // 有右子节点且还未访问cur = cur->right;}
}int main()
{// 构建一个二叉树TreeNode* root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(3);root->left->left = new TreeNode(4);root->left->right = new TreeNode(5);root->right->left = new TreeNode(6);root->right->right = new TreeNode(7);TreeNode* m = root; // 选择m和nTreeNode* n = root->right->left;// 采用非递归后序遍历,最后访问根结点,访问到目标结点n时,// 栈中所有元素均为该结点的祖先,依次出栈打印即可。postorder(m, n); // 调用后序遍历查找路径m->nreturn 0;
}
递归:
#include <iostream>using namespace std;// 二叉树结点定义
struct TreeNode
{int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};// 后序遍历查找路径m->n
bool postorder(TreeNode* root, TreeNode* n)
{// 边界情况:空结点 -> 查找失败if (!root) return false;// 递归遍历左右子树if (root == n || postorder(root->left, n) || postorder(root->right, n)) {// 如果当前结点是目标结点n,或者在左右子树中找到了目标结点// 输出当前结点的值,并返回truecout << root->val << ' ';return true;}
}int main()
{// 构建一个二叉树TreeNode* root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(3);root->left->left = new TreeNode(4);root->left->right = new TreeNode(5);root->right->left = new TreeNode(6);root->right->right = new TreeNode(7);TreeNode* m = root; // 选择m和nTreeNode* n = root->right->left;// 在后续遍历退回时访问根节点,就可以从下向上把从m到n的路径上的节点输出postorder(m, n); // 调用后序遍历查找路径m->nreturn 0;
}