首页 > 代码库 > IT公司100题-tencent-打印所有高度为2的路径
IT公司100题-tencent-打印所有高度为2的路径
问题描述：
打印所有到叶子节点长度为2的路径
10
/ \
6 16
/ \ / \
4 8 14 18
/ \ / \ \
2 5 12 15 20
/
11
打印：
[10 6 8]
[6 4 2]
[6 4 5]
[16 14 15]
[16 18 20]
[14 12 11]
分析：
1， 对于树先做先序遍历。
2， 然后针对每个节点做检查，检查的内容是，是否含有长度为2的叶子节点路径。
3， 检查的过程是，设定一个depth，同时保存当前root节点，递归遍历每个子节点，每次递归depth+1，push当前root节点，如果depth为n，当前节点为叶子节点，则打印出来，否则如果depth<n，就继续遍历子节点，跟随每次入栈操作的是:1, depth+1 2, push_back(root)。如果depth>=n，就不继续遍历，同时跟随函数调用结束出栈的操作是：1，depth-1 2，pop当前节点。
代码实现：
1 #include <iostream> 2 #include "../utility/printCollection.h" 3 using namespace std; 4 5 struct bsnode{ 6 int data; 7 bsnode* left; 8 bsnode* right; 9 }; 10 11 void add_bsnode(bsnode* &root, int value) 12 { 13 if(root == NULL) 14 { 15 bsnode* tmp = new bsnode(); 16 tmp->data =http://www.mamicode.com/ value; 17 tmp->left = NULL; 18 tmp->right = NULL; 19 root = tmp; 20 return; 21 } 22 if(value > root->data) 23 add_bsnode(root->right, value); 24 else if(value < root->data) 25 add_bsnode(root->left, value); 26 else 27 cout << "duplicate value" << endl; 28 } 29 30 void print_tree(bsnode* root) 31 { 32 if(root == NULL) 33 return; 34 if(root->left != NULL) 35 print_tree(root->left); 36 cout << root->data << " "; 37 if(root->right != NULL) 38 print_tree(root->right); 39 } 40 41 42 void check_node(bsnode* root, int n, int &depth, vector<int> &path) 43 { 44 //如果当前深度>n，不需要继续访问 45 if(depth > n || root == NULL) 46 return; 47 48 //检查前压栈当前节点，depth+1 49 path.push_back(root->data); 50 depth++; 51 52 //如果当前深度=n 53 if(depth == n) 54 if(root->left == NULL && root->right == NULL) 55 { 56 cout << "path found: " << endl; 57 printCollection(path); 58 cout << endl; 59 } 60 61 //如果当前深度<n 62 if(depth < n) 63 if(root->left != NULL) 64 check_node(root->left, n, depth, path); 65 if(root->right != NULL) 66 check_node(root->right, n, depth, path); 67 68 //检查完出栈当前节点，depth-1 69 path.pop_back(); 70 depth--; 71 return; 72 } 73 74 void print_node(bsnode* root, int n) 75 { 76 if(root == NULL) 77 return; 78 79 //每次检查前重定义depth 80 int depth = -1; 81 vector<int> path; 82 83 //每次检查前clear path 84 path.clear(); 85 86 //检查当前节点的所有叶子节点的高度 87 check_node(root, n, depth, path); 88 89 //递归检查左子树 90 print_node(root->left, n); 91 //递归检查右子树 92 print_node(root->right, n); 93 } 94 95 96 int main() 97 { 98 bsnode* root = NULL; 99 add_bsnode(root, 10); 100 add_bsnode(root, 6);101 add_bsnode(root, 16);102 add_bsnode(root, 4);103 add_bsnode(root, 8);104 add_bsnode(root, 14);105 add_bsnode(root, 18);106 add_bsnode(root, 2);107 add_bsnode(root, 5);108 add_bsnode(root, 12);109 add_bsnode(root, 15);110 add_bsnode(root, 20);111 add_bsnode(root, 11);112 113 cout << "Tree content: " << endl;114 print_tree(root);115 cout << endl << endl;116 117 int height = 2; 118 cout << "Nodes that with height " << height << " are:" << endl;119 print_node(root, height);120 cout << endl;121 }
输出：
$ ./a.exeTree content:2 4 5 6 8 10 11 12 14 15 16 18 20Nodes that with height 2 are:path found:[10 6 8]path found:[6 4 2]path found:[6 4 5]path found:[16 14 15]path found:[16 18 20]path found:[14 12 11]
IT公司100题-tencent-打印所有高度为2的路径
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。