<Data Structures/Algorithms> leetcode hot100 - 128. Convert Sorted Array to Binary Search Tree

[LeetCode Hot 100] 128. Convert Sorted Array to Binary Search Tree

Problem Link

This problem is quite interesting. At first glance, it seems simple, but a closer look reveals some subtle traps.

The expanded result is in preorder traversal order. That is, for any node, after expansion, its right subtree sequence should follow root → left subtree → right subtree, and the left and right subtrees themselves are also expanded in the same way.

So for a node, we first need to link the left subtree to the right subtree, then perform the same operation for both subtrees. This process is called Morris traversal. The method is to find the rightmost node of the left subtree and attach the right subtree to it. The correctness of this approach can be visualized by drawing a line with slope -1, essentially peeling layer by layer along this direction. A good illustration can be found on Zhihu.

After connecting the left subtree to the right, we need to perform the same operation inside the left subtree. At this point, the left subtree is actually the current node’s right child, so we move the pointer to the right child and repeat the loop. Similarly, the right subtree is handled automatically as the pointer keeps moving right and eventually reaches the original right child. The implementation is as follows:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode* cur = root;
        while(cur){
            TreeNode* leftRight = cur->left;
            if(leftRight){
                while(leftRight->right){
                    leftRight = leftRight->right;
                }
                leftRight->right = cur->right;
                cur->right = cur->left;
                cur->left = nullptr;
            }
            cur = cur->right;       
        }
    }
};

中文原文

[LeetCode hot 100] 128. 将有序数组转化为二叉搜索树

题目链接

这个题有点意思，乍一看挺简单，想一下就会发现有点点坑。

展开的结果是先序遍历的顺序，也就是说对于某个节点，展开后它的右子树这一串应该是根节点→左子树→右子树这个顺序，而左子树和右子树也是这样展开的。

所以对一个节点，我们首先要将左子树链到右子树中，再对左右子树都执行这个操作。这个过程的实现方法叫做Morris遍历，方法是找到左子树的最右节点，再将右子树接到该节点的下面。这玩意的正确性我不会证明，但是可以画一条$y=-x$的斜线，这个过程就相当于沿着这个方向一层一层剥开。知乎上找到一个挺好的示意图

每次把左子树连到右子树之后，需要再对左子树内也进行同样的操作，但是此时左子树就是我们根节点的右孩子，因此把指针移动到右孩子，重复这个循环。此外，右子树也需要执行这个操作，同样不用担心，指针一直往右移动，早晚会指向原本的右子树的根节点，也就是原来的右孩子。代码实现如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode* cur = root;
        while(cur){
            TreeNode* leftRight = cur->left;
            if(leftRight){
                while(leftRight->right){
                    leftRight = leftRight->right;
                }
                leftRight->right = cur->right;
                cur->right = cur->left;
                cur->left = nullptr;
            }
            cur = cur->right;       
        }
    }
};