二叉树中,打印根节点到指定节点的路径——后序遍历的变型解答
程序员文章站
2022-05-20 13:53:20
...
题目:二叉树中,打印根节点到指定节点的路径
此类型题目,如上或找两个指定节点的最短路径,一律要往二叉树遍历思想上靠。
此题解答即用到后序遍历的改进而来。
从二叉树中打印两个指定节点的最短路径,需要用到中序遍历。言归正传。
此题代码实现:
#include<vector>
#include<iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left, *right;
TreeNode(int x):val(x),left(nullptr),right(nullptr){}
};
vector<TreeNode*> res;
void advPostOrder(TreeNode* root,TreeNode* node) {
if (!root)//递归终止条件之一
return;
if (root == node) {//递归终止条件之二
res.push_back(node);
return;
}
if (root->left)
advPostOrder(root->left, node);
if (root->right)
advPostOrder(root->right, node);
//以下表明,数组中已存在节点,且本遍历节点的左或右儿子是数组未端节点
if (!res.empty()&&(root->left==res.back()||root->right==res.back()))
res.push_back(root);
}
int main() {
TreeNode a(1), b(2), c(3), d(4), e(5), f(6), g(7), h(8), i(9);
a.left = &b;
a.right = &c;
b.left = &d;
b.right = &e;
d.left = &f;
d.right = &g;
e.left = &h;
e.right = &i;
advPostOrder(&a, &i);
return 0;
}
上一篇: 惠普推出Linux平台的迷你型笔记本