【题目】
一颗二叉树原本是搜索二叉树,但是其中有两个节点调换了位置,使得这个二叉树不再是搜索二叉树,请找到这两个错误节点并返回。
package zyc.binaryTree; import java.util.Stack; public class P137_getTwoErrorNode { public static Node[] getTwoErrorNode(Node node) { Node[] errors = new Node[2]; if (node == null) { return errors; } // 搜索二叉树采用 中序遍历 Node pre = null; Stack<Node> nodeStack = new Stack<>(); while (node != null || !nodeStack.isEmpty()) { if (node != null) { nodeStack.add(node); node = node.left; } else { Node cur = nodeStack.pop(); if (pre != null && pre.value > cur.value) { // 第一个错误节点是 首次降序的较大节点 errors[0] = errors[0] == null ? pre : errors[0]; // 第二个错误节点是 最后一次降序的较小节点 errors[1] = cur; } pre = cur; node = cur.right; } } return errors; } public static class Node { public int value; public Node left; public Node right; public Node(int value) { this.value = value; } } }