调整搜索二叉树中的两个错误的节点

调整搜索二叉树中的两个错误的节点

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

《程序员代码面试指南》第40题 P137 难度：尉★★☆☆

（只看原问题，进阶问题难度将，解答不可能看的懂）

如果没有错误节点，那么搜索二叉树的中序遍历的节点值是一直升序的。如果有两个节点位置错了，就一定会出现降序。

出现降序有2种情况：

1. 出现2次降序，第一个错误的节点为第一次降序时较大的节点，第二个错误的节点为第二次降序时较小的节点
2. 出现1次降序，第一个错误的节点为这次降序时较大的节点，第二个错误的节点为这次降序时较小的节点

总结为：第一个错误的节点为第一次降序时较大的节点，第二个错误的节点为最后一次降序时较小的节点。

因此只需要改写一个基本的中序遍历即可。书上代码使用了非递归（栈）来进行中序遍历，代码如下：

public Node[] getTwoErrNodes(Node head) {
    Node[] errs = new Node[2];
    if (head == null) {
        return errs;
    }
    Stack stack = new Stack();
    Node pre = null;
    while (!stack.isEmpty() || head != null) {
        if (head != null) {
            stack.push(head);
            head = head.left;
        } else {
            head = stack.pop();
            if (pre != null && pre.value > head.value) {
                errs[0] = errs[0] == null ? pre : errs[0];
                errs[1] = head;
            }
            pre = head;
            head = head.right;
        }
    }
    return errs;
}