99. 恢复二叉搜索树

题意：

解题思路：

思路：
1. 中序遍历，产生的序列是严格递增的；
2. 递归找到两个数字，如果通过中序遍历得到的顺序为递减，说明前面的数字比后面的数字大，违背了中序遍历的顺序；
3. 记录前后两个递减节点，最后进行交换；

PHP代码实现：

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($val = 0, $left = null, $right = null) {
 *         $this->val = $val;
 *         $this->left = $left;
 *         $this->right = $right;
 *     }
 * }
 */
class Solution {
    /**
     * @param TreeNode $root
     * @return NULL
     */
    function recoverTree($root) {
        if ($root == null) return;
        $this->helper($root);
        $temp = $this->firstNode->val;
        $this->firstNode->val = $this->secondNode->val;
        $this->secondNode->val = $temp;
    }
    public $firstNode;
    public $secondNode;
    public $pre;
    function helper($root) {
        if ($root == null) return;
        $this->helper($root->left);
        if ($this->pre == null) $this->pre = $root;
        else {
            if ($this->pre->val > $root->val) {
                if ($this->firstNode == null) {
                    $this->firstNode = $this->pre;
                }
                $this->secondNode = $root;
            }
            $this->pre = $root;
        }
        $this->helper($root->right);
    }
}

GO代码实现：

var first, second, pre *TreeNode
func recoverTree(root *TreeNode) {
    first, second, pre = nil, nil, nil
    helper(root)
    first.Val, second.Val = second.Val, first.Val
}
func helper(root *TreeNode) {
    if root == nil {
        return
    }
    helper(root.Left)
    if pre != nil && pre.Val > root.Val {
        second = root
        if first == nil {
            first = pre
        } else {
            return
        }
    }
    pre = root
    helper(root.Right)
}