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

last modify

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

问题简述

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

思路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]]

Last updated