99_恢复二叉搜索树

99_恢复二叉搜索树

package 二叉树.二叉搜索树;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/recover-binary-search-tree/
 * 
 * @author Huangyujun
 *
 */
public class _99_恢复二叉搜索树 {
    // 恢复：即更改有问题的两个结点后，调整整棵树
    //方式1 ：先中序遍历将有序的元素存放到容器里，然后遍历容器找出两个有问题的结点。
    //套路：要从出题人角度出发，为啥他要给你一个二叉搜索树~【因为中序遍历比较有特点，整个树也非常有特点，都是 根大于左子树， 小于右子树】
    // 套路：给你一棵二叉搜索树，第一反应（二叉搜索树特点：左子树小于根，右子树大于根，然后中序遍历是递增）
    class Solution {
        public void recoverTree(TreeNode root) {
            List<TreeNode> list = new ArrayList<TreeNode>();
            dfs(root,list);
            TreeNode x = null;
            TreeNode y = null;
            //扫描 list的结果，找出可能存在错误交换的节点x和y【利用升序，第一个错误结点：是出现递减的前一个【突然变大，导致后边那个结点受到影响，与之关系的递增被破坏】，第二个错误结点，是出现递减的后一个【突然变小，导致前边一个结点受到影响，与之关系的递增被破坏】】
            for(int i=0;i<list.size()-1;++i) {
                if(list.get(i).val>list.get(i+1).val) {
                    y = list.get(i+1);
                    if(x==null) {
                        x = list.get(i);
                    }
                }
            }
            //如果x和y不为空，则交换这两个节点值，恢复二叉搜索树
            if(x!=null && y!=null) {
                int tmp = x.val;
                x.val = y.val;
                y.val = tmp;
            }
        }

        //中序遍历二叉树，并将遍历的结果保存到list中        
        private void dfs(TreeNode node,List<TreeNode> list) {
            if(node==null) {
                return;
            }
            dfs(node.left,list);
            list.add(node);
            dfs(node.right,list);
        }
    }
    
    //方法2：迭代遍历（其实是第一种方法的简单优化一下而已，将第一种方法的中序递归改成中序迭代，将第一种存储数据元素于容器list，再找到问题结点优化成直接找，标记出两个问题结点，然后进行交换）
    //思路是 中序遍历记录时直接标记出两个有错误的结点【然后再进行交换，就不用把数据都放到容器里，然后遍历容器里的元素后才标出来有问题的元素】
    class Solution3 {
        //用两个变量x，y来记录需要交换的节点
        private TreeNode x = null;
        private TreeNode y = null;
        private TreeNode pre = null;
        public void recoverTree(TreeNode root) {
            dfs(root);
            //如果x和y都不为空，说明二叉搜索树出现错误的节点，将其交换
            if(x!=null && y!=null) {
                int tmp = x.val;
                x.val = y.val;
                y.val = tmp;
            }
        }
        
        //中序遍历二叉树，并比较上一个节点(pre)和当前节点的值，如果pre的值大于当前节点值，则记录下这两个节点
        private void dfs(TreeNode node) {
            if(node==null) {
                return;
            }
            dfs(node.left);
            if(pre==null) {
                pre = node;
            }
            else {
                if(pre.val>node.val) {
                    y = node;
                    if(x==null) {
                        x = pre;
                    }
                }
                pre = node;
            }
            dfs(node.right);
        }
    }


}