建设一个网站首先需要,有没有在线做动图的网站,网站流量运营,龙岗区建设局网站Leetcode99 给定一个 二叉搜索树#xff0c;其中两个节点被交换#xff0c;写一个程序恢复这颗BST. 只想到了时间复杂度O#xff08;n#xff09;空间复杂度O#xff08;h#xff09; h为树高的解法#xff0c;还没想到空间O(1#xff09;的解法。 交换的情况只有两种其中两个节点被交换写一个程序恢复这颗BST. 只想到了时间复杂度On空间复杂度Oh h为树高的解法还没想到空间O(1的解法。 交换的情况只有两种 case1 两个节点在树中中序遍历序列相邻 case2 两个节点在树中中序遍历序列不相邻。 只要三个指针 Pre first second 即可记录两种case class Solution {
public: TreeNode *first; TreeNode *second; TreeNode *pre; void inOrder(TreeNode *root){ if (rootNULL) return; inOrder(root-left); if (pre NULL){pre root;} else { if (pre-val root-val){ if (firstNULL) {first pre;} second root; } pre root; } inOrder(root-right); } void recoverTree(TreeNode *root) { // Start typing your C/C solution below // DO NOT write int main() function pre NULL; first NULL; second NULL; inOrder(root); int val; val first-val; first-valsecond-val; second-valval; return; }
};转载于:https://www.cnblogs.com/heisenberg-/p/6596332.html
