找到搜索二叉树中两个错误的节点
问题简述
一棵二叉树原本是搜索二叉树,但是其中有两个节点调换了位置,使得这棵二叉树不再是搜索二叉树,请按升序输出这两个错误节点的值。(每个节点的值各不相同)
思路1:辅助数组
二叉搜索树的中序遍历结果是有序的;
本题等价于找出有序数组中两个调换的数字;
考虑两种情况:1)交换数字相邻;2)不相邻;
思路2:DFS 的过程中判断
定义
pre
表示上一个节点;初始化为
None
;每次访问节点时更新;
要点:
(写法1)如果
pre
是一个值类型,那么需要使用全局变量,即在不同递归状态统一;(写法2)如果是一个引用类型,那么可以作为参数传递;
Last updated