力扣DAY40-45 | 热100 | 二叉树：直径、层次遍历、有序数组-＞二叉搜索树、验证二叉搜索树、二叉搜索树中第K小的元素、右视图

前言

简单、中等 √ 好久没更了，感觉二叉树来回就那些。有点变懒要警醒，不能止步于笨方法！！

二叉树的直径

我的题解

遍历每个节点，左节点最大深度+右节点最大深度+当前节点=当前节点为中心的直径。如果左节点深度更大，向左遍历，直到直径不再更新。

class Solution {
public://最大深度int deepOfTree(TreeNode* root){if (!root)return 0;return max(deepOfTree(root->left), deepOfTree(root->right))+1;}int diameterOfBinaryTree(TreeNode* root) {TreeNode* node = root;int d = 0;int maxd = 0;while (node){int deepl = deepOfTree(node->left);int deepr = deepOfTree(node->right);d = deepl + deepr;maxd = max(maxd, d);if (deepl > deepr)node = node->left;else if (deepl < deepr)node = node->right;elsebreak;}return maxd;}
};

 上述方法耗时较长，原因是求最大深度和遍历每个节点的直径步骤重复了。优化后把直径设为全局节点。保留遍历最大深度函数，遍历过程中顺便更新直径maxd = max(maxd, deepl+deepr);

class Solution {
public:int maxd = 0;//最大深度int deepOfTree(TreeNode* node){if (!node)return 0;int deepl = deepOfTree(node->left);int deepr = deepOfTree(node->right);maxd = max(maxd, deepl+deepr);return max(deepl, deepr)+1;}int diameterOfBinaryTree(TreeNode* root) {deepOfTree(root);return maxd;}
};

官解

与笔者的方法二一致

心得

最大深度的延申题。

二叉树的层次遍历

我的题解

广度优先搜索，用一个队列存节点和深度，根据深度保存答案。

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {if (!root) return {};vector<vector<int>> ans;queue<pair<TreeNode*, int>> q;q.push({root, 0});while (!q.empty()){TreeNode* node = q.front().first;int level = q.front().second;if (level >= ans.size())ans.push_back({node->val});elseans[level].push_back(node->val);if (node->left) q.push({node->left, level + 1});if (node->right) q.push({node->right, level + 1});q.pop();}return ans;}
};

官解

广度优先搜索
思路和算法

我们可以用广度优先搜索解决这个问题。

我们可以想到最朴素的方法是用一个二元组 (node, level) 来表示状态，它表示某个节点和它所在的层数，每个新进队列的节点的 level 值都是父亲节点的 level 值加一。最后根据每个点的 level 对点进行分类，分类的时候我们可以利用哈希表，维护一个以 level 为键，对应节点值组成的数组为值，广度优先搜索结束以后按键 level 从小到大取出所有值，组成答案返回即可。

考虑如何优化空间开销：如何不用哈希映射，并且只用一个变量 node 表示状态，实现这个功能呢？

我们可以用一种巧妙的方法修改广度优先搜索：

首先根元素入队
当队列不为空的时候
求当前队列的长度 
依次从队列中取 元素进行拓展，然后进入下一次迭代
它和普通广度优先搜索的区别在于，普通广度优先搜索每次只取一个元素拓展，而这里每次取 元素。在上述过程中的第 i 次迭代就得到了二叉树的元素。

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector <vector <int>> ret;if (!root) {return ret;}queue <TreeNode*> q;q.push(root);while (!q.empty()) {int currentLevelSize = q.size();ret.push_back(vector <int> ());for (int i = 1; i <= currentLevelSize; ++i) {auto node = q.front(); q.pop();ret.back().push_back(node->val);if (node->left) q.push(node->left);if (node->right) q.push(node->right);}}return ret;}
};

心得

官解用了一个巧妙的方法节省了节点的深度信息。简单来说就是同时把同一层的节点遍历完。用currentLevelSize = q.size();记录当前层有多少个节点，然后内嵌循环把这些节点都遍历并且输出。后续我也尝试了这个方法但是漏了记录当前层节点的关键步骤。之后会留意..

将有序数组转换为二叉搜索树

我的题解

有点像分治法，取中点作为当前节点建树，左子树取左边数组作为新的数组建树，右子树取右边。

class Solution {
public:TreeNode* sort(vector<int>& nums, int l, int r){if (l > r)return nullptr;int mid = (l + r)/2;TreeNode* root = new TreeNode(nums[mid]);root->left = sort(nums, l, mid-1);root->right = sort(nums, mid+1, r);return root; }TreeNode* sortedArrayToBST(vector<int>& nums) {if (nums.empty())return nullptr;TreeNode* root = new TreeNode();root = sort(nums, 0, nums.size()-1);return root;}
};

官解

官解与笔者思路一致，只是策略不同（左、右，随机节点为子节点）

心得

有序数组转换为二叉搜索树还是比较简单的，可以研究下无序数组如何转换并且维护，应该跟最大堆差不多？

验证二叉搜索树

我的题解

左右子树有三个点要验证：1）子树值与当前节点值比对；2）子树是否也是二叉搜索树；3）子树的最大（右）/小（左）节点值与当前节点值比对。凡是一点不符合直接返回false，否则返回true。

class Solution {
public:bool isValidBST(TreeNode* root) {if (!root)return true;if (root->left){if (root->val <= root->left->val)return false;if (!isValidBST(root->left))return false;if (root->left->right){TreeNode* node = root->left->right;while (node->right){node = node->right;}if (root->val <= node->val)return false;}}if (root->right){if (root->val >= root->right->val)return false;if (!isValidBST(root->right))return false;if (root->right->left){TreeNode* node = root->right->left;while (node->left){node = node->left;}if (root->val >= node->val)return false;}}return true;}
};

官解

递归

要解决这道题首先我们要了解二叉搜索树有什么性质可以给我们利用，由题目给出的信息我们可以知道：如果该二叉树的左子树不为空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左右子树也为二叉搜索树。

这启示我们设计一个递归函数 helper(root, lower, upper) 来递归判断，函数表示考虑以 root 为根的子树，判断子树中所有节点的值是否都在 (l,r) 的范围内（注意是开区间）。如果 root 节点的值 val 不在 (l,r) 的范围内说明不满足条件直接返回，否则我们要继续递归调用检查它的左右子树是否满足，如果都满足才说明这是一棵二叉搜索树。

那么根据二叉搜索树的性质，在递归调用左子树时，我们需要把上界 upper 改为 root.val，即调用 helper(root.left, lower, root.val)，因为左子树里所有节点的值均小于它的根节点的值。同理递归调用右子树时，我们需要把下界 lower 改为 root.val，即调用 helper(root.right, root.val, upper)。

函数递归调用的入口为 helper(root, -inf, +inf)， inf 表示一个无穷大的值。

class Solution {
public:bool helper(TreeNode* root, long long lower, long long upper) {if (root == nullptr) {return true;}if (root -> val <= lower || root -> val >= upper) {return false;}return helper(root -> left, lower, root -> val) && helper(root -> right, root -> val, upper);}bool isValidBST(TreeNode* root) {return helper(root, LONG_MIN, LONG_MAX);}
};

中序遍历

基于方法一中提及的性质，我们可以进一步知道二叉搜索树「中序遍历」得到的值构成的序列一定是升序的，这启示我们在中序遍历的时候实时检查当前节点的值是否大于前一个中序遍历到的节点的值即可。如果均大于说明这个序列是升序的，整棵树是二叉搜索树，否则不是，下面的代码我们使用栈来模拟中序遍历的过程。

可能有读者不知道中序遍历是什么，我们这里简单提及。中序遍历是二叉树的一种遍历方式，它先遍历左子树，再遍历根节点，最后遍历右子树。而我们二叉搜索树保证了左子树的节点的值均小于根节点的值，根节点的值均小于右子树的值，因此中序遍历以后得到的序列一定是升序序列。

class Solution {
public:bool isValidBST(TreeNode* root) {stack<TreeNode*> stack;long long inorder = (long long)INT_MIN - 1;while (!stack.empty() || root != nullptr) {while (root != nullptr) {stack.push(root);root = root -> left;}root = stack.top();stack.pop();// 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树if (root -> val <= inorder) {return false;}inorder = root -> val;root = root -> right;}return true;}
};

心得

两个官解都是好方法。递归：输入最大值和最小值，遍历每个节点的值，在限定范围内，左子树的最大值更新为当前节点值，右子树的最小值更新为当前节点值，子树都为二叉搜索树则返回true；迭代；迭代：中序遍历，由于二叉搜索树遍历出来应该是升序排列，故如果当前节点小于等于前一节点，直接返回false。这个题考察对二叉搜索树的理解，我的方法虽然绕过了long long但是太笨了！

二叉搜索树中第K小的元素

我的题解

中序遍历到第k个元素，return。

class Solution {
public:int kthSmallest(TreeNode* root, int k) {stack<TreeNode*> forder;TreeNode* node = root;vector<int> ans;int count = 0;forder.push(node);while(!forder.empty()){while(node){forder.push(node);node = node->left;}node = forder.top();ans.push_back(node->val);forder.pop();node = node->right;count++;if (count == k)break;}return ans[k-1];}
};

官解

中序遍历与笔者一致，不赘述。平衡二叉搜索树的方法太长了，粗略看每个函数也不太难，性价比不高，以后再学习吧。

记录子树的结点数

我们之所以需要中序遍历前 k 个元素，是因为我们不知道子树的结点数量，不得不通过遍历子树的方式来获知。

因此，我们可以记录下以每个结点为根结点的子树的结点数，并在查找第 k 小的值时，使用如下方法搜索：

令 node 等于根结点，开始搜索。

对当前结点 node 进行如下操作：

如果 node 的左子树的结点数 left 小于 k−1，则第 k 小的元素一定在 node 的右子树中，令 node 等于其的右子结点，k 等于 k−left−1，并继续搜索；
如果 node 的左子树的结点数 left 等于 k−1，则第 k 小的元素即为 node ，结束搜索并返回 node 即可；
如果 node 的左子树的结点数 left 大于 k−1，则第 k 小的元素一定在 node 的左子树中，令 node 等于其左子结点，并继续搜索。
在实现中，我们既可以将以每个结点为根结点的子树的结点数存储在结点中，也可以将其记录在哈希表中。

class MyBst {
public:MyBst(TreeNode *root) {this->root = root;countNodeNum(root);}// 返回二叉搜索树中第k小的元素int kthSmallest(int k) {TreeNode *node = root;while (node != nullptr) {int left = getNodeNum(node->left);if (left < k - 1) {node = node->right;k -= left + 1;} else if (left == k - 1) {break;} else {node = node->left;}}return node->val;}private:TreeNode *root;unordered_map<TreeNode *, int> nodeNum;// 统计以node为根结点的子树的结点数int countNodeNum(TreeNode * node) {if (node == nullptr) {return 0;}nodeNum[node] = 1 + countNodeNum(node->left) + countNodeNum(node->right);return nodeNum[node];}// 获取以node为根结点的子树的结点数int getNodeNum(TreeNode * node) {if (node != nullptr && nodeNum.count(node)) {return nodeNum[node];}else{return 0;}}
};class Solution {
public:int kthSmallest(TreeNode* root, int k) {MyBst bst(root);return bst.kthSmallest(k);}
};

心得

中序遍历的迭代写法还需要再巩固，以当前节点为判断条件，而不是以下一节点为判断条件。记录子树的结点数的方法：首先要用一个哈希表记录每个节点有多少颗子树，计算过程定义count函数，获取过程定义get函数。然后遍历每个节点，如果子树数量小于k，移到right，如果等于k，返回当前节点，大于k，移到left。感觉这个方法不是很能复用到其他题目上，但是count和get（哈希）这种分开的方式很值得我学习，是一种安全高效的获取方式。

二叉树的右视图

我的题解

对二叉树进行层次遍历，把每一层的最后一个元素取出放入ans容器中。

class Solution {
public:vector<int> rightSideView(TreeNode* root) {if (!root)return {};queue<pair<TreeNode*, int>> q;vector<vector<int>> bfs;vector<int> ans;TreeNode* node = root;int level = 0;q.push({node, level});while (!q.empty()){node = q.front().first;level = q.front().second;q.pop();if (node->left) q.push({node->left, level+1});if (node->right) q.push({node->right, level+1});if (level >= bfs.size()) bfs.push_back({node->val});else bfs[level].push_back(node->val);}for (int i = 0; i < bfs.size(); i++){ans.push_back(bfs[i].back());}return ans;}
};

官解

广度优先搜索/层次遍历与笔者思路一致，不赘述。

深度优先搜索

我们对树进行深度优先搜索，在搜索过程中，我们总是先访问右子树。那么对于每一层来说，我们在这层见到的第一个结点一定是最右边的结点。

算法

这样一来，我们可以存储在每个深度访问的第一个结点，一旦我们知道了树的层数，就可以得到最终的结果数组。

上图表示了问题的一个实例。红色结点自上而下组成答案，边缘以访问顺序标号。

class Solution {
public:vector<int> rightSideView(TreeNode* root) {unordered_map<int, int> rightmostValueAtDepth;int max_depth = -1;stack<TreeNode*> nodeStack;stack<int> depthStack;nodeStack.push(root);depthStack.push(0);while (!nodeStack.empty()) {TreeNode* node = nodeStack.top();nodeStack.pop();int depth = depthStack.top();depthStack.pop();if (node != NULL) {// 维护二叉树的最大深度max_depth = max(max_depth, depth);// 如果不存在对应深度的节点我们才插入if (rightmostValueAtDepth.find(depth) == rightmostValueAtDepth.end()) {rightmostValueAtDepth[depth] =  node -> val;}nodeStack.push(node -> left);nodeStack.push(node -> right);depthStack.push(depth + 1);depthStack.push(depth + 1);}}vector<int> rightView;for (int depth = 0; depth <= max_depth; ++depth) {rightView.push_back(rightmostValueAtDepth[depth]);}return rightView;}
}; 

心得

层次遍历的解法是直观的解法。深度优先搜索的解法则是定义了哈希表记录每个深度最右的节点。维护一个节点栈和深度栈，然后对二叉树进行后序遍历，如果当前深度没有最右节点，则放入ans中。这个解法其实也与层次遍历类似，只是显式地用栈来维护深度信息。