每日题解:LeetCode 897. 递增顺序搜索树

题目地址

题目描述

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

ex1.jpg

示例 1:

输入: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]

ex2.jpg

示例 2:


输入:root = [5,1,7]
输出:[1,null,5,null,7]
提示:

树中节点数的取值范围是 [1, 100]
0 <= Node.val <= 1000

解法

数组保存中序遍历

void inorder(struct TreeNode *node, struct TreeNode* res[], int *resSize) {
    if (node) {
    inorder(node->left, res, resSize);
    res[(*resSize)++] = node;
    inorder(node->right, res, resSize);
    }
}

struct TreeNode *increasingBST(struct TreeNode *root) {
   struct TreeNode* res[100];
    int resSize = 0;
    inorder(root, res, &resSize);
    for(int i=0;i<resSize;i++){
        res[i]->left = NULL;
        res[i]->right = res[i + 1];
    }

 res[resSize-1]->left = NULL;
 res[resSize-1]->right =NULL;
 return res[0];
}

遍历中修改节点指向

    private TreeNode resNode;

    public TreeNode increasingBST(TreeNode root) {
        TreeNode dummyNode = new TreeNode(-1);
        resNode = dummyNode;
        inorder(root);
        return dummyNode.right;
    }

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

        inorder(node.right);
    }

解题思路

数组保存中序遍历

因为中序遍历就是一个递增顺序,只要把

  1. 先中序遍历,把结果放在数组中
  2. 然后遍历数组,把当前遍历节点的左子树设置为 null,把遍历节点的右子树设置下一个数组节点
  3. 遍历结束,将数组最后一个节点的左右树都设置null

中序遍历中修改节点指向

数组保存中序遍历,相当于两次遍历二叉树,,比较浪费空间

如果我们在中序遍历的过程中,

  • 把当前节点左子树设置为 null;
  • resNode.right 设置为当前遍历的节点 ;
  • 把当前 resNode指向当前节点。

这个解法可以理解为模拟操作
image20210425231907866.png

可以参考,这个题解的思路,分享二叉树三种遍历方式的模板

更早的文章

每日题解:LeetCode 213. 打家劫舍 II

题目地址题目描述你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。给定一个代表每个房屋存放金额的非负整数数组…

继续阅读