《Cracking the Coding Interview》——第4章：树和图—

《Cracking the Coding Interview》——第4章：树和图——题目6

2014-03-19 04:16

题目：找出一棵二叉搜索树中的中序遍历后继节点，每个节点都有指针指向其父节点。

解法1：分两种情况：向下走时，先右后左；向上走时，先左后右。如果目标节点有右子树，就向右下走，否则往左上走。话说，如果没有父指针的话，还是一口气进行各中序遍历，求出所有结果比较有效率。

代码：

  1 // 4.6 Find the inorder successor of a node in the binary tree.
  2 // online algorithm with parent pointer.
  3 #include <cstdio>
  4 #include <unordered_map>
  5 using namespace std;
  6 
  7 struct TreeNode {
  8     int val;
  9     TreeNode *left;
 10     TreeNode *right;
 11     TreeNode *parent;
 12     
 13     TreeNode(int _val = 0): val(_val), left(nullptr), right(nullptr), parent(nullptr) {};
 14 };
 15 
 16 void constructBinaryTree(TreeNode *&root)
 17 {
 18     int val;
 19     
 20     scanf("%d", &val);
 21     if (val <= 0) {
 22         root = nullptr;
 23     } else {
 24         root = new TreeNode(val);
 25 
 26         constructBinaryTree(root->left);
 27         constructBinaryTree(root->right);
 28         if (root->left != nullptr) {
 29             root->left->parent = root;
 30         }
 31         if (root->right != nullptr) {
 32             root->right->parent = root;
 33         }
 34     }
 35 }
 36 
 37 TreeNode *inorderSuccessor(TreeNode *node)
 38 {
 39     if (node == nullptr) {
 40         return nullptr;
 41     }
 42     
 43     TreeNode *result;
 44     if (node->right != nullptr) {
 45         result = node->right;
 46         while (result->left != nullptr) {
 47             result = result->left;
 48         }
 49         
 50         return result;
 51     } else {
 52         result = node;
 53         while(true) {
 54             if (result->parent == nullptr) {
 55                 return nullptr;
 56             } else if (result == result->parent->left) {
 57                 return result->parent;
 58             } else {
 59                 result = result->parent;
 60             }
 61         }
 62     }
 63 }
 64 
 65 void inorderTraversal(TreeNode *root)
 66 {
 67     if (root == nullptr) {
 68         return;
 69     }
 70     
 71     inorderTraversal(root->left);
 72     TreeNode *next_node = inorderSuccessor(root);
 73     if (next_node != nullptr) {
 74         printf("%d %d
", root->val, next_node->val);
 75     } else {
 76         printf("%d #
", root->val);
 77     }
 78     inorderTraversal(root->right);
 79 }
 80 
 81 void clearBinaryTree(TreeNode *&root) {
 82     if (root == nullptr) {
 83         return;
 84     } else {
 85         clearBinaryTree(root->left);
 86         clearBinaryTree(root->right);
 87         delete root;
 88         root = nullptr;
 89     }
 90 }
 91 
 92 int main()
 93 {
 94     TreeNode *root;
 95     
 96     while (true) {
 97         constructBinaryTree(root);
 98         if (root == nullptr) {
 99             break;
100         }
101         
102         inorderTraversal(root);
103         
104         clearBinaryTree(root);
105     }
106     
107     return 0;
108 }

解法2：一次性进行中序遍历的离线做法。

代码：

  1 // 4.6 Find the inorder successor of a node in the binary tree.
  2 // offline algorithm with inorder traversal.
  3 #include <cstdio>
  4 #include <unordered_map>
  5 using namespace std;
  6 
  7 struct TreeNode {
  8     int val;
  9     TreeNode *left;
 10     TreeNode *right;
 11     TreeNode *parent;
 12     
 13     TreeNode(int _val = 0): val(_val), left(nullptr), right(nullptr), parent(nullptr) {};
 14 };
 15 
 16 void constructBinaryTree(TreeNode *&root)
 17 {
 18     int val;
 19     
 20     scanf("%d", &val);
 21     if (val <= 0) {
 22         root = nullptr;
 23     } else {
 24         root = new TreeNode(val);
 25 
 26         constructBinaryTree(root->left);
 27         constructBinaryTree(root->right);
 28         if (root->left != nullptr) {
 29             root->left->parent = root;
 30         }
 31         if (root->right != nullptr) {
 32             root->right->parent = root;
 33         }
 34     }
 35 }
 36 
 37 void inorderTraversal(TreeNode *root, vector<TreeNode *> &inorder_list)
 38 {
 39     if (root == nullptr) {
 40         return;
 41     }
 42     inorderTraversal(root->left, inorder_list);
 43     inorder_list.push_back(root);
 44     inorderTraversal(root->right, inorder_list);
 45 }
 46 
 47 TreeNode *inorderSuccessor(TreeNode *node, unordered_map<TreeNode *, TreeNode *> &dict)
 48 {
 49     if (dict.find(node) == dict.end()) {
 50         return nullptr;
 51     } else {
 52         return dict[node];
 53     }
 54 }
 55 
 56 void clearBinaryTree(TreeNode *&root) {
 57     if (root == nullptr) {
 58         return;
 59     } else {
 60         clearBinaryTree(root->left);
 61         clearBinaryTree(root->right);
 62         delete root;
 63         root = nullptr;
 64     }
 65 }
 66 
 67 int main()
 68 {
 69     TreeNode *root;
 70     unordered_map<TreeNode *, TreeNode *> dict;
 71     vector<TreeNode *> inorder_list;
 72     int i;
 73     
 74     while (true) {
 75         constructBinaryTree(root);
 76         if (root == nullptr) {
 77             break;
 78         }
 79         
 80         inorderTraversal(root, inorder_list);
 81         for (i = 0; i < (int)inorder_list.size() - 1; ++i) {
 82             dict[inorder_list[i]] = inorder_list[i + 1];
 83         }
 84         dict[inorder_list[i]] = nullptr;
 85         
 86         TreeNode *next_node;
 87         for (i = 0; i < (int)inorder_list.size(); ++i) {
 88             next_node = inorderSuccessor(inorder_list[i], dict);
 89             if (next_node != nullptr) {
 90                 printf("%d %d
", inorder_list[i]->val, next_node->val);
 91             } else {
 92                 printf("%d #
", inorder_list[i]->val);
 93             }
 94         }
 95         
 96         inorder_list.clear();
 97         dict.clear();
 98         clearBinaryTree(root);
 99     }
100     
101     return 0;
102 }