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

![last modify](https://img.shields.io/static/v1?label=last%20modify\&message=2022-10-14%2014%3A59%3A33\&color=yellowgreen\&style=flat-square) [![](https://img.shields.io/static/v1?label=\&message=%E4%B8%AD%E7%AD%89\&color=yellow\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#中等) [![](https://img.shields.io/static/v1?label=\&message=%E7%89%9B%E5%AE%A2\&color=green\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#牛客) [![](https://img.shields.io/static/v1?label=\&message=%E4%BA%8C%E5%8F%89%E6%A0%91/%E6%A0%91\&color=blue\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#二叉树树)

> [找到搜索二叉树中两个错误的节点\_牛客题霸\_牛客网](https://www.nowcoder.com/practice/4582efa5ffe949cc80c136eeb78795d6)

**问题简述**

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

**思路1：辅助数组**

* 二叉搜索树的中序遍历结果是有序的；
* 本题等价于找出有序数组中两个调换的数字；
  * 考虑两种情况：1）交换数字相邻；2）不相邻；

<details>

<summary><strong>Python</strong></summary>

```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]]
```

</details>

**思路2：DFS 的过程中判断**

* 定义 `pre` 表示上一个节点；
  * 初始化为 `None`；
  * 每次访问节点时更新；
* 要点：
  * （写法1）如果 `pre` 是一个值类型，那么需要使用全局变量，即在不同递归状态统一；
  * （写法2）如果是一个引用类型，那么可以作为参数传递；

<details>

<summary><strong>写法1：使用全局变量</strong></summary>

```python
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]]
```

</details>

<details>

<summary><strong>写法2：使用引用类型</strong></summary>

```python
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]]
```

</details>