找到搜索二叉树中两个错误的节点

找到搜索二叉树中两个错误的节点_牛客题霸_牛客网

问题简述

一棵二叉树原本是搜索二叉树，但是其中有两个节点调换了位置，使得这棵二叉树不再是搜索二叉树，请按升序输出这两个错误节点的值。(每个节点的值各不相同)

思路1：辅助数组

• 二叉搜索树的中序遍历结果是有序的；

• 本题等价于找出有序数组中两个调换的数字；

  • 考虑两种情况：1）交换数字相邻；2）不相邻；

Python

class Solution:
    def findError(self , root: TreeNode) -> List[int]:
        
        arr = []
        
        def dfs(x):
            if not x:
                return
            dfs(x.left)
            arr.append(x.val)
            dfs(x.right)
        
        dfs(root)
        
        ret = []
        pre = arr[0]
        for i in range(1, len(arr)):
            if arr[i] < pre:
                ret.append([arr[i], pre])
            pre = arr[i]
        
        if len(ret) == 1:
            return ret[0]
        else:  # 显然是后面的小，前面的大
            return [ret[1][0], ret[0][1]]

思路2：DFS 的过程中判断

• 定义 pre 表示上一个节点；

  • 初始化为 None；

  • 每次访问节点时更新；

• 要点：

  • （写法1）如果 pre 是一个值类型，那么需要使用全局变量，即在不同递归状态统一；

  • （写法2）如果是一个引用类型，那么可以作为参数传递；

写法1：使用全局变量

class Solution:
    def findError(self , root: TreeNode) -> List[int]:
        
        ret = []

        # pre 是一个全局变量
        self.pre = None
        
        def dfs(x):
            if not x: return
            
            dfs(x.left)
            if self.pre is not None and self.pre > x.val:
                ret.append([x.val, self.pre])
            self.pre = x.val
            dfs(x.right)
        
        dfs(root)
        
        if len(ret) == 1:
            return ret[0]
        else:  # 显然是后面的小，前面的大
            return [ret[1][0], ret[0][1]]

写法2：使用引用类型

class Solution:
    def findError(self , root: TreeNode) -> List[int]:
        
        ret = []
        
        # pre 是一个引用类型的参数
        def dfs(x, pre):
            if not x: return
            
            dfs(x.left, pre)
            if pre.val is not None and pre.val > x.val:
                ret.append([x.val, pre.val])
            pre.val = x.val
            dfs(x.right, pre)
        
        dfs(root, ListNode(None))
        
        if len(ret) == 1:
            return ret[0]
        else:  # 显然是后面的小，前面的大
            return [ret[1][0], ret[0][1]]