专门做win7系统的网站,成都企业展厅设计成都企业展厅设计公司,广西专业网站建设,免费注册域名和服务器99. 恢复二叉搜索树题意在BST中存在两个元素被交换了#xff0c;现在需要把这两个元素给交换回来变成BST。解题思路将其转为数组#xff0c;并且排好序后重新赋值给树结点#xff1b;使用变量pre来保存访问的前一个结点#xff0c;因为是中序遍历#xff0c;所以前面一个结… 99. 恢复二叉搜索树题意在BST中存在两个元素被交换了现在需要把这两个元素给交换回来变成BST。解题思路将其转为数组并且排好序后重新赋值给树结点使用变量pre来保存访问的前一个结点因为是中序遍历所以前面一个结点必然是小于当前结点的并且用两个变量维护错误的两个结点最后将这两个结点的值进行交换需要注意的是可能存在父结点和子结点交换的情况所以在开始的时候都保存下来实现class Solution(object): mistake1 None mistake2 None pre None def recoverTree(self, root): :type root: TreeNode :rtype: void Do not return anything, modify root in-place instead. def dfs(node): if not node: return dfs(node.left) if self.pre and node.val self.pre.val: if not self.mistake1: self.mistake1 self.pre self.mistake2 node self.pre node dfs(node.right) dfs(root) if self.mistake1 and self.mistake2: self.mistake1.val, self.mistake2.val self.mistake2.val, self.mistake1.val def recoverTree(self, root): :type root: TreeNode :rtype: void Do not return anything, modify root in-place instead. node_list, val_list [], [] def dfs(node): if not node: return dfs(node.left) node_list.append(node) val_list.append(node.val) dfs(node.right) dfs(root) val_list.sort() for idx, val in enumerate(val_list): node_list[idx].val val_list[idx] def recoverTree(self, root): 迭代实现 :type root: TreeNode :rtype: void Do not return anything, modify root in-place instead. cur, pre root, None first, second None, None stack [] while cur or stack: if cur: stack.append(cur) cur cur.left else: node stack.pop() if pre and pre.val node.val: if not first: first pre second node pre node cur node.right first.val, second.val second.val, first.val 转载于:https://www.cnblogs.com/George1994/p/7507989.html
