本文主要是介绍LeetCode - 897. 递增顺序查找树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
写在前面的话：
虽然这是一个简单题，但是做这道题目的时候顺便写了通过给定数组新建二叉树，打印二叉树等，掉了好几次坑，做一个简单总结
1）普通二叉树不一定是完全二叉树，不要以为是二叉树就是完全二叉树；
2）层序遍历跟（先、中、后序遍历）都不同，像个猪一样大意了，导致在打印二叉树哪儿对结果纠结了很久；
3）后序遍历的时候，最后一个结点的左、右子节点都不一定为 nullptr， 如果有特殊需要记得处理，比如将最后一个结点的 left/right 都置位 nullptr；
4）中序遍历的时候，最有一个结点的左节点不一定为 nullptr，但是右节点一定为 nullptr，记得对 left处理（同上）；
5）前序遍历的时候，最有一个结点的左、右子节点肯定为 nullptr；
描述
给你一个树，请你 按中序遍历 重新排列树，使树中最左边的结点现在是树的根，并且每个结点没有左子结点，只有一个右子结点。
示例 ：
输入：[5,3,6,2,4,null,8,1,null,null,null,7,9]
5
/ \
3 6
/ \ \
2 4 8
/ / \
1 7 9
输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
1
\
2
\
3
\
4
\
5
\
6
\
7
\
8
\
9
提示：
给定树中的结点数介于 1 和 100 之间。
每个结点都有一个从 0 到 1000 范围内的唯一整数值。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/increasing-order-search-tree/
求解
class Solution {public:// 方法一，原地修改，时间复杂度O(N), 空间复杂度O(1)TreeNode *increasingBST(TreeNode *root) {auto head = new TreeNode();p = head;inOrdered(root);p->left = nullptr; // 注意中序遍历对最后一个结点left的处理auto res = head->right;delete head;return res;}// 方法二，使用辅助空间存储中序遍历得到的节点,时间复杂度O(N), 空间复杂度O(N)TreeNode *increasingBST_1e(TreeNode *root) {if (!root) {return root;}std::vector<TreeNode *> record;inOrdered(root, record);const int num = record.size();for (int i = 0; i < num - 1; ++i) {record[i]->left = nullptr;record[i]->right = record[i + 1];}// 注意这个处理，中序遍历最后一个结点的左节点不一定为空，即left可能还有指向其他节点，务必赋值nullptrrecord[num - 1]->left = nullptr;return record[0];}private:TreeNode *p = nullptr;// 中序遍历void inOrdered(TreeNode *root) {if (!root) {return;}inOrdered(root->left);p->right = root;p = p->right;p->left = nullptr;inOrdered(root->right);}// 按照中序遍历将节点存储到record中void inOrdered(TreeNode *root, std::vector<TreeNode *> &record) {if (root) {inOrdered(root->left, record);record.push_back(root);inOrdered(root->right, record);}}};
这篇关于LeetCode - 897. 递增顺序查找树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
