Determine K-th Node In An Inorder Traversal

来源：EPI, Facebook Onsite

原帖：EPI 6.6 pg. 233

题目：
It is trivial to find the k-th node that appears in an inorder traversal with O(n) time complexity. However, with additional information on each node, you can do better. Design a function that efficiently computes the k-th node appearing in an inorder traversal. Specifically, your function should take as input a binary tree T and an integer k. Each node has a size field, which is the number of nodes in the subtree rooted at that node. What is the time complexity of your function?

代码：

 //Part I: TreeNodeSize  
 struct TreeNodeSize {  
   int val;  
   int size;  
     TreeNodeSize* left;  
     TreeNodeSize* right;  
     TreeNodeSize(int v) : data(d), size(1), left(NULL), right(NULL) {}  
 };  
   
 // Each node with a size variable  
 TreeNodeSize* find_kth_node_binary_tree(TreeNodeSize* root, int k) {  
   while (root && k) {  
     int left_size = root->left ? root->left->size : 0;  
     if (left_size < k - 1) {  
       k -= (left_size + 1);  
       root = root->right;  
     } else if (left_size == k - 1) {  
       return root;  
     } else {  
       root = root->left;  
     }  
   }  
   return NULL;  
   //throw length_error("no k-th node in binary tree");  
 }  
   
 //Part II: TreeNode structure  
 struct TreeNode {  
   int val;  
   TreeNode* left;  
   TreeNode* right;  
   TreeNode(int v) : val(v), left(NULL), right(NULL) {}  
 };  
   
 TreeNode* find_kth_node(TreeNode* root, int k, int& n) {  
   if (!root) return NULL;  
   TreeNode* node = find_kth_node(root->left, k, n);  
   if (node) return node;  
   n += 1;  
   if (n == k) return root;  
   return find_kth_node(root->right, k, n);  
 }  
   
 TreeNode* find_kth_node_binary_tree(TreeNode* root, int k) {  
   int n = 0;  
   return find_kth_node(root, k, n);  
 }