leetcode学习笔记897 Increasing Order Search Tree

leetcode学习笔记897

• 开始之前
• 问题
• 思考

开始之前

在做leetcode的每日一题的时候做到了这一次.其实很简单, 是个easy的题目.
可能是因为很久没做了tree的题目了, 这个题目竟然卡住了.

无地自容.

天冷难道把脑子也一起冻住了吗?

问题

Increasing Order Search Tree

Given the root of a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only one right child.

Example 1:

Input: root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

Example 2:

Input: root = [5,1,7]
Output: [1,null,5,null,7]

Constraints:

• The number of nodes in the given tree will be in the range [1, 100].
• 0 <= Node.val <= 1000

思考

仔细看题,其实就是中序排列node而已.

方法1

先中序遍历Tree,得到所有的val ,然后再按照顺序依次生成新的Tree即可.

时间复杂度O(n).
空间复杂度O(n).

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode increasingBST(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        inorder(root, list);
        TreeNode node = new TreeNode(), cur = node;
        for(int val : list){
            cur.right = new TreeNode(val);
            cur = cur.right;
        }
        return node.right;
    }
    
    public void inorder(TreeNode node, List<Integer> list){
        if(node == null)
            return;
        inorder(node.left, list);
        list.add(node.val);
        inorder(node.right, list);
    }
}

方法2

更快的方法是不用list存储, 在inorder遍历的同时对Tree进行修改.

有一点需要注意的就是每次更新的时候要注意更新上层node的right, 并且在更新结束之后将本层node保存起来以便下层使用.

时间复杂度O(n).
空间复杂度O(1).

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    
    TreeNode pre;
    
    public TreeNode increasingBST(TreeNode root) {
        TreeNode node = new TreeNode();
        pre = node;
        inorder(root);
        return node.right;
    }
    
    public void inorder(TreeNode node){
        if(node == null)
            return;
        inorder(node.left);
        node.left = null;
        pre.right = node;
        pre = node;
        inorder(node.right);
    }
}