芜湖手机网站开发,wordpress 屏蔽升级,上海公司注册查询官网,电商销售渠道有哪些文章目录 题目标题和出处难度题目描述要求示例数据范围 解法一思路和算法代码复杂度分析 解法二思路和算法代码复杂度分析 解法三思路和算法代码复杂度分析 后记 题目
标题和出处
标题#xff1a;递增顺序搜索树
出处#xff1a;897. 递增顺序搜索树
难度
3 级
题目描述… 文章目录 题目标题和出处难度题目描述要求示例数据范围 解法一思路和算法代码复杂度分析 解法二思路和算法代码复杂度分析 解法三思路和算法代码复杂度分析 后记 题目
标题和出处
标题递增顺序搜索树
出处897. 递增顺序搜索树
难度
3 级
题目描述
要求
给定二叉搜索树的根结点 root \texttt{root} root请你按中序遍历将其重新排列为递增顺序搜索树使树中最左边的结点成为树的根结点并且每个结点没有左子结点只有右子结点。
示例
示例 1 输入 root [5,3,6,2,4,null,8,1,null,null,null,7,9] \texttt{root [5,3,6,2,4,null,8,1,null,null,null,7,9]} root [5,3,6,2,4,null,8,1,null,null,null,7,9] 输出 [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9] \texttt{[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]} [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
示例 2 输入 root [5,1,7] \texttt{root [5,1,7]} root [5,1,7] 输出 [1,null,5,null,7] \texttt{[1,null,5,null,7]} [1,null,5,null,7]
数据范围
树中结点数目在范围 [1, 100] \texttt{[1, 100]} [1, 100] 内 0 ≤ Node.val ≤ 1000 \texttt{0} \le \texttt{Node.val} \le \texttt{1000} 0≤Node.val≤1000
解法一
思路和算法
这道题要求按照二叉搜索树中序遍历的顺序将二叉搜索树重新排列为递增顺序搜索树。最直观的解法是对二叉搜索树中序遍历并记录中序遍历的结点顺序然后更改结点之间的指针指向。对于每个结点将其左子结点指针设为 null \text{null} null将其右子结点指针设为中序遍历顺序的后一个结点其中中序遍历顺序的最后一个结点的右子结点指针也设为 null \text{null} null。
新的根结点为中序遍历序列的首个结点返回新的根结点。
代码
下面的代码为递归实现二叉搜索树中序遍历的做法。
class Solution {ListTreeNode traversal new ArrayListTreeNode();public TreeNode increasingBST(TreeNode root) {inorder(root);int size traversal.size();for (int i 0; i size; i) {TreeNode node traversal.get(i);node.left null;node.right i size - 1 ? null : traversal.get(i 1);}return traversal.get(0);}public void inorder(TreeNode node) {if (node null) {return;}inorder(node.left);traversal.add(node);inorder(node.right);}
}下面的代码为迭代实现二叉搜索树中序遍历的做法。
class Solution {public TreeNode increasingBST(TreeNode root) {ListTreeNode traversal new ArrayListTreeNode();DequeTreeNode stack new ArrayDequeTreeNode();TreeNode node root;while (!stack.isEmpty() || node ! null) {while (node ! null) {stack.push(node);node node.left;}node stack.pop();traversal.add(node);node node.right;}int size traversal.size();for (int i 0; i size; i) {node traversal.get(i);node.left null;node.right i size - 1 ? null : traversal.get(i 1);}return traversal.get(0);}
}复杂度分析 时间复杂度 O ( n ) O(n) O(n)其中 n n n 是二叉搜索树的结点数。中序遍历需要访问每个结点一次展开为链表也需要访问每个结点一次。 空间复杂度 O ( n ) O(n) O(n)其中 n n n 是二叉搜索树的结点数。中序遍历的递归实现和迭代实现都需要栈空间栈空间取决于二叉搜索树的高度最坏情况下二叉搜索树的高度是 O ( n ) O(n) O(n)存储中序遍历序列需要 O ( n ) O(n) O(n) 的空间。
解法二
思路和算法
解法一需要访问每个结点两次首先得到中序遍历序列然后重新排列。其实中序遍历和重新排列可以同步完成只需要访问每个结点一次。
在中序遍历的迭代实现中维护上一个访问的结点 prev \textit{prev} prev 和当前访问的结点 curr \textit{curr} curr初始时 prev null \textit{prev} \text{null} prevnull。对于每个结点当 prev ≠ null \textit{prev} \ne \text{null} prevnull 时将 prev \textit{prev} prev 的左子结点指针设为 null \text{null} null将 prev \textit{prev} prev 的右子结点指针设为 curr \textit{curr} curr。访问当前结点 curr \textit{curr} curr 之后将 prev \textit{prev} prev 的值设为 curr \textit{curr} curr继续访问下一个结点直到遍历结束。
遍历结束时 prev \textit{prev} prev 为最后一个访问的结点将其左子结点指针和右子结点指针都设为 null \text{null} null。新的根结点为首个访问的结点返回新的根结点。
代码
class Solution {public TreeNode increasingBST(TreeNode root) {DequeTreeNode stack new ArrayDequeTreeNode();TreeNode newRoot null;TreeNode prev null, curr root;while (!stack.isEmpty() || curr ! null) {while (curr ! null) {stack.push(curr);curr curr.left;}curr stack.pop();if (newRoot null) {newRoot curr;}if (prev ! null) {prev.left null;prev.right curr;}prev curr;curr curr.right;}prev.left null;prev.right null;return newRoot;}
}复杂度分析 时间复杂度 O ( n ) O(n) O(n)其中 n n n 是二叉搜索树的结点数。每个结点都被访问一次。 空间复杂度 O ( n ) O(n) O(n)其中 n n n 是二叉搜索树的结点数。空间复杂度主要是栈空间栈内元素个数不超过 n n n。
解法三
思路和算法
解法一和解法二都需要使用栈空间。还有一种使用常数空间的解法不使用栈或者其他数据结构存储结点只改变结点之间的指针关系。
为了方便处理创建哑结点将二叉搜索树的根结点作为哑结点的右子结点则哑结点没有左子结点只有右子结点。从哑结点开始遍历则遍历到的结点即当前结点一定没有左子结点。如果当前结点有右子结点则执行如下操作。 如果右子结点没有左子结点则将当前结点移动到右子结点继续对剩下的结点重新排列。 如果右子结点有左子结点则找到右子结点的前驱结点将右子结点作为前驱结点的右子结点将右子结点的左子结点作为当前结点的右子结点。
重复上述操作直到当前结点的右子结点为空此时二叉搜索树中的结点排列完毕哑结点的右子结点为新的根结点返回新的根结点。
考虑示例 1 的二叉搜索树其中序遍历顺序是 [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ] [1,2,3,4,5,6,7,8,9] [1,2,3,4,5,6,7,8,9]。此处省略哑结点。 当前结点为哑结点右子结点为结点 5 5 5结点 5 5 5 的左子结点为结点 3 3 3因此找到结点 5 5 5 的前驱结点 4 4 4将以结点 5 5 5 为根结点的子树移动到结点 4 4 4 的右子树的位置将以结点 3 3 3 为根结点的子树移动到哑结点的右子树的位置。 当前结点为哑结点右子结点为结点 3 3 3结点 3 3 3 的左子结点为结点 2 2 2因此找到结点 3 3 3 的前驱结点 2 2 2将以结点 3 3 3 为根结点的子树移动到结点 2 2 2 的右子树的位置将以结点 2 2 2 为根结点的子树移动到哑结点的右子树的位置。 当前结点为哑结点右子结点为结点 2 2 2结点 2 2 2 的左子结点为结点 1 1 1因此找到结点 2 2 2 的前驱结点 1 1 1将以结点 2 2 2 为根结点的子树移动到结点 1 1 1 的右子树的位置将以结点 1 1 1 为根结点的子树移动到哑结点的右子树的位置。 结点 1 1 1 至结点 6 6 6 的左子结点都为空因此将当前结点移动到结点 6 6 6。
当前结点为结点 6 6 6右子结点为结点 8 8 8结点 8 8 8 的左子结点为结点 7 7 7因此找到结点 8 8 8 的前驱结点 7 7 7将以结点 8 8 8 为根结点的子树移动到结点 7 7 7 的右子树的位置将以结点 7 7 7 为根结点的子树移动到结点 6 6 6 的右子树的位置。 结点 7 7 7 至结点 9 9 9 的左子结点都为空因此将当前结点移动到结点 9 9 9。
此时当前结点的右子结点为空二叉搜索树中的结点排列完毕。
代码
class Solution {public TreeNode increasingBST(TreeNode root) {TreeNode dummyRoot new TreeNode(0, null, root);TreeNode node dummyRoot;while (node.right ! null) {TreeNode right node.right;if (right.left ! null) {TreeNode predecessor right.left;while (predecessor.right ! null) {predecessor predecessor.right;}predecessor.right right;TreeNode next right.left;right.left null;node.right next;} else {node node.right;}}return dummyRoot.right;}
}复杂度分析 时间复杂度 O ( n ) O(n) O(n)其中 n n n 是二叉搜索树的结点数。遍历和展开过程中每个结点都被访问一次寻找前驱结点的过程中每个结点最多被访问一次因此每个结点最多被访问两次。 空间复杂度 O ( 1 ) O(1) O(1)。
后记
读者也许已经发现解法三和莫里斯遍历非常相似。和莫里斯遍历相比这道题不需要将前驱结点的右指针指向当前结点而是将当前结点的右子树移动到前驱结点的右子树的位置因此解法三可以看成莫里斯遍历的简化版。
