标准一： 打印边界节点
输入：
{1,2,3,0,4,5,6,7,8,9,10,0,0,0,0,0,11,12,0,0,0,13,14,15,16}
输出：
1 2 4 7 11 13 14 15 16 12 10 6 3
// // main.cpp // 打印二叉树的边界节点 // // Created by zjl on 16/9/14. // Copyright © 2016年 zjl. All rights reserved. // #include <iostream> #include <vector> #include <queue> using namespace std; struct TreeNode{ int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; TreeNode* create(vector<int>vec){ int num = vec.size(); TreeNode* root = new TreeNode(vec[0]); queue<TreeNode*> q; q.push(root); int i = 1; while(i <= num){ TreeNode* t = q.front(); q.pop(); if(vec[i] > 0){ t->left = new TreeNode(vec[i]); q.push(t->left); } else t->left = NULL; i++; if(i<= num){ if(vec[i] > 0){ t->right = new TreeNode(vec[i]); q.push(t->right); } else t->right = NULL; i++; } } return root; } int getheight(TreeNode* root, int l){ if(root == NULL) return l; return max(getheight(root->left, l+1), getheight(root->right, l+1)); } void setedge(TreeNode* root, int l, vector<vector<TreeNode*>>&edgeMap){ if(root == NULL) return; if(edgeMap[l][0] == NULL) edgeMap[l][0] = root; edgeMap[l][1] = root; setedge(root->left, l+1, edgeMap); setedge(root->right, l+1, edgeMap); } void printleafnode(TreeNode* root, int l, vector<vector<TreeNode*>>&edgeMap){ if(root == NULL) return; if(root->left == NULL && root->right == NULL && root != edgeMap[l][0] && root != edgeMap[l][1]) cout<<root->val<<" "; printleafnode(root->left, l+1, edgeMap); printleafnode(root->right, l+1, edgeMap); } void solve(TreeNode* root){ if(root == NULL) return; int height = getheight(root, 0); vector<vector<TreeNode*>> edgeMap(height, vector<TreeNode*>(2,NULL)); setedge(root, 0, edgeMap); //打印左边界 for(int i = 0; i < edgeMap.size(); i++) cout<<edgeMap[i][0]->val<<" "; //打印既不是左边界，又不是右边界的叶子节点 printleafnode(root, 0, edgeMap); //打印右边界，但不是左边界的节点 for(int i = edgeMap.size()-1; i >= 0; i--){ if(edgeMap[i][0] != edgeMap[i][1]) cout<<edgeMap[i][1]->val<<" "; } cout<<endl; } int main(int argc, const char * argv[]) { // insert code here... vector<int>num={1,2,3,0,4,5,6,7,8,9,10,0,0,0,0,0,11,12,0,0,0,13,14,15,16}; TreeNode* root = create(num); solve(root); return 0; }
