2014-03-19 04:16
题目：找出一棵二叉搜索树中的中序遍历后继节点，每个节点都有指针指向其父节点。
解法1：分两种情况：向下走时，先右后左；向上走时，先左后右。如果目标节点有右子树，就向右下走，否则往左上走。话说，如果没有父指针的话，还是一口气进行各中序遍历，求出所有结果比较有效率。
代码：
// 4.6 Find the inorder successor of a node in the binary tree.
// online algorithm with parent pointer.
#include <cstdio>
#include <unordered_map>
using namespace std; struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode *parent; TreeNode(int _val = ): val(_val), left(nullptr), right(nullptr), parent(nullptr) {};
}; void constructBinaryTree(TreeNode *&root)
{
int val; scanf("%d", &val);
if (val <= ) {
root = nullptr;
} else {
root = new TreeNode(val); constructBinaryTree(root->left);
constructBinaryTree(root->right);
if (root->left != nullptr) {
root->left->parent = root;
}
if (root->right != nullptr) {
root->right->parent = root;
}
}
} TreeNode *inorderSuccessor(TreeNode *node)
{
if (node == nullptr) {
return nullptr;
} TreeNode *result;
if (node->right != nullptr) {
result = node->right;
while (result->left != nullptr) {
result = result->left;
} return result;
} else {
result = node;
while(true) {
if (result->parent == nullptr) {
return nullptr;
} else if (result == result->parent->left) {
return result->parent;
} else {
result = result->parent;
}
}
}
} void inorderTraversal(TreeNode *root)
{
if (root == nullptr) {
return;
} inorderTraversal(root->left);
TreeNode *next_node = inorderSuccessor(root);
if (next_node != nullptr) {
printf("%d %d\n", root->val, next_node->val);
} else {
printf("%d #\n", root->val);
}
inorderTraversal(root->right);
} void clearBinaryTree(TreeNode *&root) {
if (root == nullptr) {
return;
} else {
clearBinaryTree(root->left);
clearBinaryTree(root->right);
delete root;
root = nullptr;
}
} int main()
{
TreeNode *root; while (true) {
constructBinaryTree(root);
if (root == nullptr) {
break;
} inorderTraversal(root); clearBinaryTree(root);
} return ;
}
解法2：一次性进行中序遍历的离线做法。
代码：
// 4.6 Find the inorder successor of a node in the binary tree.
// offline algorithm with inorder traversal.
#include <cstdio>
#include <unordered_map>
using namespace std; struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode *parent; TreeNode(int _val = ): val(_val), left(nullptr), right(nullptr), parent(nullptr) {};
}; void constructBinaryTree(TreeNode *&root)
{
int val; scanf("%d", &val);
if (val <= ) {
root = nullptr;
} else {
root = new TreeNode(val); constructBinaryTree(root->left);
constructBinaryTree(root->right);
if (root->left != nullptr) {
root->left->parent = root;
}
if (root->right != nullptr) {
root->right->parent = root;
}
}
} void inorderTraversal(TreeNode *root, vector<TreeNode *> &inorder_list)
{
if (root == nullptr) {
return;
}
inorderTraversal(root->left, inorder_list);
inorder_list.push_back(root);
inorderTraversal(root->right, inorder_list);
} TreeNode *inorderSuccessor(TreeNode *node, unordered_map<TreeNode *, TreeNode *> &dict)
{
if (dict.find(node) == dict.end()) {
return nullptr;
} else {
return dict[node];
}
} void clearBinaryTree(TreeNode *&root) {
if (root == nullptr) {
return;
} else {
clearBinaryTree(root->left);
clearBinaryTree(root->right);
delete root;
root = nullptr;
}
} int main()
{
TreeNode *root;
unordered_map<TreeNode *, TreeNode *> dict;
vector<TreeNode *> inorder_list;
int i; while (true) {
constructBinaryTree(root);
if (root == nullptr) {
break;
} inorderTraversal(root, inorder_list);
for (i = ; i < (int)inorder_list.size() - ; ++i) {
dict[inorder_list[i]] = inorder_list[i + ];
}
dict[inorder_list[i]] = nullptr; TreeNode *next_node;
for (i = ; i < (int)inorder_list.size(); ++i) {
next_node = inorderSuccessor(inorder_list[i], dict);
if (next_node != nullptr) {
printf("%d %d\n", inorder_list[i]->val, next_node->val);
} else {
printf("%d #\n", inorder_list[i]->val);
}
} inorder_list.clear();
dict.clear();
clearBinaryTree(root);
} return ;
}