"Coding Interview Guide" -- 找到搜索二叉树中两个错误的节点

【题目】

　　一棵二叉树原本是搜索二叉树，但是其中有两个节点调换了位置，使得这棵二叉树不再是搜索二叉树，请找到这两个错误节点并返回。已知二叉树中所有的节点值都不一样，给定二叉树的头节点head，返回一个长度为2的二叉树节点类型的数组errs，errs[0]表示一个错误节点，errs[1]表示另一个错误节点

【搜索二叉树】

　　　又称二叉查找树，二叉排序树，它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有节点的值均小于其根节点的值；若它的右子树不空，则右子树上所有节点的值均大于其根节点的值，它的左右子树也分别为二叉搜索树

 　　　 import java.util.Stack;

 1     public Node[] getTwoErrNodes(Node head)
 2     {
 3         Node[] errs = new Node[2];
 4         if(head == null)
 5         {    
 6             return errs;
 7         }
 8 
 9         Stack<Integer> stack = new Stack<>();
10         Node pre = null;
11         while(!stack.empty() || head != null)
12         {
13             if(head != null)
14             {
15                 stack.push(head);
16                 head = head.left;
17             }
18             else
19             {
20                 head = stack.pop();
21                 if(pre != null && pre.value > head.value)
22                 {
23                     errs[0] = errs[0] == null ? pre : errs[0];
24                     errs[1] = head;
25                 }
26                 pre = head;
27                 head = head.right;
28             }
29         }
30         return errs;
31     }

来源：左程云《程序员代码面试指南》