《程序员代码面试指南》it名企算法与数据结构题目最优解（第二版）刷题笔记15

由于之前看了牛客网的数据结构和算法的课程知道了左神，现在找到了这本书当作入门书做做吧，虽然书的题解都是java实现的，但好在用c++实现难度不大

第三章 二叉树问题

第一题：打印二叉树的边界节点

给定一颗二叉树的头节点 head，按照如下两种标准分别实现二叉树边界节点的逆时针打印。

标准一：

1、头节点为边界节点；

2、叶节点为边界节点；

3、如果节点在其所在的层中是最左或者最右的，那么也是边界节点。

标准二：

1、头节点为边界节点；

2、叶节点为边界节点；

3、树左边界延伸下去的路径为边界节点；

4、树右边界延伸下去的路径为边界节点。

例如，如下图所示的树。

按标准一打印的结果为：1，2，4，7，11，13，14，15，16，12，10，6，3

按标准一打印的结果为：1，2，4，7，13，14，15，16，10，6，3

【要求】：

1、如果节点数为 N，两种标准实现的时间复杂度要求都为 O(N)，额外的空间复杂度要求为 O(h)，h 为二叉树的高度；

2、两种标准都要求逆时针顺序不重复的打印所有边界节点。

标准一：

1.得到树高

2.遍历树建立存放了左右边界节点的vector

3.打印左节点

4.打印既不是左边界，也不是右边界的叶子节点

5.打印右节点

struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class Solution {public:void printEdge1(TreeNode* root) {int hight = 0;//得到树高，方便打印hight = getHight(root, 0);//不想用数组，用默认值初始化的vector代替vector<int> vector1(hight*2);//打印左边界for (int i = 0; i < hight; i++) {cout << vector1[i * 2 + 0] << " ";}//打印既不是左边界，也不是右边界的叶子节点，leaf means 叶子printLeafNotInVector(root,0,vector1);//最后逆序打印右边界,但不是左边界的节点（棒状结构就会出现右边界等于左边界的情况）for (int i = hight-1; i >= 0; i--) {if (vector1[i * 2 + 1] != vector1[i * 2 + 0])cout << vector1[i * 2 + 1] << " ";}return;}//getHight的正确方法int getHight(TreeNode* root, int hight) {if (root == NULL)return hight;return max(getHight(root->left, hight + 1), getHight(root->right, hight + 1));}//实质上是遍历树的同时将vector完成void setTheArray(TreeNode* root, int hight, vector<int> vector1) {if (root == nullptr)return;vector1[hight * 2 + 0] = vector1[hight * 2 + 0] == 0 ? root->val : vector1[hight * 2 + 0];vector1[hight * 2 + 1] = root->val;setTheArray(root->left, hight + 1, vector1);setTheArray(root->right, hight + 1, vector1);}//实质是遍历树的同时找出既不是左边界，也不是右边界的叶子节点，leaf means 叶子void printLeafNotInVector(TreeNode* root,int hight,vector<int> vector1) {if (root == nullptr)return;if (root->left == nullptr&&root->right == nullptr&&vector1[hight * 2 + 0] != root->val&&vector1[hight * 2 + 1] != root->val)cout << root->val<<" ";printLeafNotInVector(root->left, hight + 1, vector1);printLeafNotInVector(root->right, hight + 1, vector1);}};

标准二

1.打印完棒状结构

2.为了做到逆时针两个遍历分别是中左右 左右中

struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class Solution {public:void printEdge2(TreeNode* root) {if (root == nullptr)return;cout << root->val << "";if (root->left != nullptr&&root->right != nullptr) {printLeftNode(root->left,true);printRightNode(root->right, true);}//这个if else是为了打印棒状结构else printEdge2(root->left != nullptr ? root->left : root->right);}//左中右遍历void printLeftNode(TreeNode* root,bool print) {if (root == nullptr)return;//同时将叶节点打印if (print || (root->left == nullptr&&root->right == nullptr))cout << root->val << " ";printLeftNode(root->left, print);printLeftNode(root->right, root->left == nullptr ? true : false);};//左右中遍历void printRightNode(TreeNode* root, bool print) {if (root == nullptr)return;//同时将叶节点打印printRightNode(root->left, root->right == nullptr ? true : false);printRightNode(root->right, print);if (print || (root->left == nullptr&&root->right == nullptr))cout << root->val << " ";};};