1 #include <iostream> 2  3 struct ThreadTreeNode { 4     int val; 5     bool ltag; /* 0 for link, 1 for thread */ 6     bool rtag; 7     ThreadTreeNode *left; 8     ThreadTreeNode *right; 9     ThreadTreeNode(int v = -1) : val(v), ltag(0), rtag(0), left(NULL), right(NULL) { }10 };11 12 class Solution {13 public:14     void *inorderThreadMirror(ThreadTreeNode *root) {15         if(!root) return NULL;16         ThreadTreeNode *prev = NULL;17         ThreadTreeNode *curr = root;18         while(curr) {19             if(!curr->left) {20                 curr->ltag = 1; /* no left child threaded it */21                 curr->left = prev; /* if curr is the first node in inorder, its prev is NULL */22                 prev = curr;23                 curr = curr->right;24             }25             else {26                 ThreadTreeNode *temp = curr->left;27                 while(temp->right && temp->right != curr) temp = temp->right;28                 if(!temp->right) { /* has not been visited */29                     temp->rtag = 1;30                     temp->right = curr;31                     curr = curr->left;32                 }33                 else { /* has been visited */34                     prev = curr;35                     curr = curr->right;36                 }37             }38         }39     }40     void inorderTraversal(ThreadTreeNode *root) {41         while(root && root->ltag != 1) root = root->left; /* find the first node in inorder */42         while(root) {43             std::cout << root->val << "  ";44             if(!root->right) break; /* right node in NULL, says that its the last node */45             if(root->rtag == 1) /* thread */46                 root = root->right;47             else { /* link */48                 root = root->right;49                 while(root && root->ltag != 1) root = root->left;50             }51         }52         std::cout << std::endl;53     }54 };55 56 int main() {57     ThreadTreeNode *root = new ThreadTreeNode(0);58     root->left = new ThreadTreeNode(1);59     root->right = new ThreadTreeNode(2);60     root->left->left = new ThreadTreeNode(3);61     root->left->right = new ThreadTreeNode(4);62     root->left->right->left = new ThreadTreeNode(5);63     root->left->right->right = new ThreadTreeNode(6);64     Solution s;65     s.inorderThreadMirror(root);66     s.inorderTraversal(root);67     return 0;68 }

 1 #include <iostream> 2  3 struct TreeNode { 4     int val; 5     TreeNode *left; 6     TreeNode *right; 7     TreeNode(int v = -1) : val(v), left(NULL), right(NULL) { }  8 }; 9 10 class Solution {11 public:12     Solution() {r_max = 0;} 13 14     int maxDistanceDFS(TreeNode *root) {15         dfs(root);16         return r_max;17     }   18     int maxDistance(TreeNode *root) {19         if(!root) return 0;20         int a = maxDep(root->left) + maxDep(root->right);21         int b = maxDistance(root->left);22         int c = maxDistance(root->right);23         return std::max(std::max(a, b), c);    24     }   25     int r_max;26 private:27     int maxDep(TreeNode *root) {28         if(!root) return 0;29         return std::max(maxDep(root->left), maxDep(root->right)) + 1;30     }   31     int dfs(TreeNode *root) {32         if(!root) return 0;33         int l = dfs(root->left);34         int r = dfs(root->right);35         r_max = std::max(r_max, l + r); 36         return l > r ? l + 1 : r + 1;37     }   38 };39 40 int main() {41     TreeNode *root = new TreeNode(1);42     root->right = new TreeNode(3);43     root->right->left = new TreeNode(4);44     root->right->right = new TreeNode(5);45     root->right->left->left = new TreeNode(6);46     root->right->left->right = new TreeNode(7);47     root->right->right->right = new TreeNode(8);48     std::cout << (new Solution)->maxDistanceDFS(root) << std::endl;49     std::cout << (new Solution)->maxDistance(root) << std::endl;50     return 0;51 }

 1 #include <iostream> 2  3 struct TreeNode { 4     int val; 5     TreeNode *left; 6     TreeNode *right; 7     TreeNode(int v = -1) : val(v), left(NULL), right(NULL) { } 8 }; 9 10 class Solution {11 public:12     TreeNode *commonForefather(TreeNode *root, TreeNode *childa, TreeNode *childb) {13         if(isHere(root->left, childa) && isHere(root->left, childb)) {14             if(root->left == childa || root->left == childb)15                 return root;16             return commonForefather(root->left, childa, childb);17         }18         else if(isHere(root->right, childa) && isHere(root->right, childb)) {19             if(root->right == childa || root->right == childb)20                 return root;21             return commonForefather(root->right, childa, childb);22         }23         else24             return root;25     }26 private:27     bool isHere(TreeNode *root, TreeNode *child) {28         if(root == child)29             return true;30         if(root == NULL)31             return false;32         return isHere(root->left, child) || isHere(root->right, child);33     }34 };35 36 int main() {37     TreeNode *root = new TreeNode(1);38     root->left = new TreeNode(2);39     root->right = new TreeNode(3);40     root->right->left = new TreeNode(4);41     root->right->left->left = new TreeNode(5);42     root->right->left->right = new TreeNode(6);43     std::cout << (new Solution)->commonForefather(root, root->right->left->left, root->right->left)->val << std::endl;44     return 0;45 }

 1 #include <iostream> 2 #include <queue> 3  4 struct TreeNode{ 5     int val; 6     TreeNode *left; 7     TreeNode *right; 8     TreeNode(int v = -1) : val(v), left(NULL), right(NULL) { } 9 };10 11 class Solution {12 public:13     int biTreeDep(TreeNode *root) {14         if(!root) return 0;15         return std::max(biTreeDep(root->left), biTreeDep(root->right)) + 1;16     }17     int biTreeWidth(TreeNode *root) {18         if(!root) return 0;19         std::queue<TreeNode *> que;20         int maxWidth = 0;21         int curWidth = 0;22         que.push(root);23         que.push(NULL);24         while(!que.empty()) {25             while(que.front()) {26                 TreeNode *curr = que.front();27                 que.pop();28                 curWidth++;29                 if(curr->left) que.push(curr->left);30                 if(curr->right) que.push(curr->right);31             }32             maxWidth = std::max(maxWidth, curWidth);33             curWidth = 0;34             que.pop();35             if(que.empty()) break;36             que.push(NULL);37         }38         return maxWidth;39     }40 };41 42 int main() {43     TreeNode *root = new TreeNode(1);44     root->left = new TreeNode(2);45     root->right = new TreeNode(3);46     root->right->right = new TreeNode(4);47     root->right->right->left = new TreeNode(5);48     root->right->right->left->right = new TreeNode(6);49     Solution s;50     std::cout << s.biTreeDep(root) << std::endl;51     std::cout << s.biTreeWidth(root) << std::endl;52     return 0;53 }

 1 #include <iostream> 2 #include <vector> 3 #include <queue> 4 #include <map> 5 using namespace std; 6  7 typedef unsigned int uint; 8 struct HuffTreeNode { 9     uint weight;10     HuffTreeNode *lchild;11     HuffTreeNode *rchild;12     HuffTreeNode *parent;13     HuffTreeNode(uint w = 0) : weight(w), lchild(NULL), rchild(NULL), parent(NULL) { }14 };15 struct Cmp {16     bool operator() (const HuffTreeNode *a, const HuffTreeNode *b) {17         return a->weight > b->weight;18     }19 };20 class Solution {21 public:22     HuffTreeNode* createHuffmanCodingTree(const vector<uint> &weight) {23         priority_queue<HuffTreeNode *, vector<HuffTreeNode *>, Cmp > pri_que;24         HuffTreeNode *prev = NULL;25         HuffTreeNode *curr = NULL;26         for(int i = 0; i < weight.size(); i++)27             pri_que.push(new HuffTreeNode(weight[i]));28         while(!pri_que.empty()) {29             prev = pri_que.top(), pri_que.pop();30             if(pri_que.empty()) break;31             curr = pri_que.top(), pri_que.pop();32             HuffTreeNode *parent = new HuffTreeNode(prev->weight + curr->weight);33             parent->lchild = prev->lchild ? curr : prev;34             parent->rchild = prev->lchild ? prev : curr;35             prev->parent = curr->parent = parent;36             pri_que.push(parent);37         }38         this->root = prev;39         return prev; 40     }41     void createHuffmanEncodeMap() {42         string bits;43         HuffTreeNode *curr = this->root;44         while(curr) {45             if(!curr->lchild) {46                 encode_map[curr->weight] = bits;47                 curr = curr->rchild;48             }49             else {50                 HuffTreeNode *temp = curr->lchild;51                 int backlevel = 1;52                 while(temp->rchild && temp->rchild != curr) temp = temp->rchild, backlevel++;53                 if(!temp->rchild) {54                     /* visit curr */55                     bits += "0";56                     temp->rchild = curr;57                     curr = curr->lchild;58                 }59                 else {60                     /* trace back to "root" node */61                     bits = bits.substr(0, bits.size() - backlevel); 62                     bits += "1";63                     temp->rchild = NULL;64                     curr = curr->rchild;65                 }66             }67         }68     }69 private:70     map<uint, string> encode_map;71     map<string, uint> decode_map;72     HuffTreeNode *root;73 };74 75 int main(int argc, char **argv) {76     vector<uint> v_ui;77     v_ui.push_back(5);78     v_ui.push_back(29);79     v_ui.push_back(7);80     v_ui.push_back(8);81     v_ui.push_back(14);82     v_ui.push_back(23);83     v_ui.push_back(3);84     v_ui.push_back(11);85     Solution s;86     s.createHuffmanCodingTree(v_ui);87     s.createHuffmanEncodeMap();88     for(int i = 0; i < v_ui.size(); i++)89         cout << v_ui[i] << " : " << s.encode_map[v_ui[i]] << endl;90     return 0;91 }