LeetCode展平二叉搜索树

剑指 Offer II 052. 展平二叉搜索树

给你一棵二叉搜索树，请 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。

输入：root = [5,3,6,2,4,null,8,1,null,null,null,7,9] 输出:[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

来源：力扣（LeetCode）

将原本的二叉搜索树先按中序遍历一遍，记录其节点。 中序遍历的遍历顺序是左子树，根节点，右子树 然后将列表中记录的节点按顺序再构成只有右节点的树。

中序遍历的大致思路： 给出root，应该先访问其左子节点，而对于左子节点也是一样的遍历，也就是先访问左子节点的左子节点； 对于什么时候将节点加入列表，那要等遇到叶节点，叶节点没有子节点，所以直接要return，同时该节点也被加入到列表里面；每次return就会有节点加入列表 当一个节点被加入到列表里面，就要访问其右子节点，同样的方法； 最后就会得到中序遍历的结果，并且存储在列表里面。

遍历列表，构造树： 增强for遍历res集合； 此时需要注意，一开始的根节点还没有被赋值，所以一开始令cur和ress都是-1； 并且cur不断增加其右子树直至最后的叶节点，最后返回的应该是ress.right，也就是新构建的树的根节点。

class Solution {
    public TreeNode increasingBST(TreeNode root) {
        List res = new ArrayList();
        inorder(root,res);

        TreeNode ress = new TreeNode(-1);
        TreeNode cur = ress;
        for(int i:res){
            cur.right= new TreeNode(i);
            cur=cur.right;
        }
        return ress.right;

    }

    public void inorder(TreeNode node,List res){
        if(node==null){
            return ;
        }
        inorder(node.left,res);
        res.add(node.val);
        inorder(node.right,res);
    }
}

思路想明白了过程就不难。

还有一种更简单一点的方法就是在中序遍历的过程当中改变节点的指向，使其直接变成所要求的树。

分析可知，中序遍历的结果就是所需要的res的遍历结果，也就是中序遍历的两个节点之间有关系，已经遍历过的节点的右孩子是下一个将要遍历的节点，也就是说上一个已经遍历过的节点的右孩子是当前节点。

所以只需要在中序遍历的同时将节点之间的指向改变即可。

最后返回的应该是根节点（所以需要先有一个TreeNode来记录一下，令ress.right保存根节点，ress为-1即可），而中序遍历的时候节点最终会回到根节点。

class Solution {
    TreeNode res;
    public TreeNode increasingBST(TreeNode root) {
        TreeNode ress = new TreeNode(-1);
        res = ress;
        inorder(root);
        return ress.right;

    }

    public void inorder(TreeNode node){
        if(node==null){
            return ;
        }
        inorder(node.left);

        res.right=node;
        node.left=null;
        res=node;
        
        inorder(node.right);
    }
}

需要注意： 1.应该有一个节点要记录根节点，先初始化一个节点为-1，令这个节点的右孩子是最终树的根节点，最终返回它的右孩子节点即可，如果直接返回遍历完之后的res的话，就只会返回叶子节点。 2.中序遍历时什么时候改指向，也就是已经确定该节点的子孩子为空或者已经遍历过，且该节点的右孩子还没有被遍历时。

将中序遍历想明白之后，题目就没那么难了。