16ms c++ solution, recursive


  • 0
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
     
     // Suppose that the current node is 2, left is 3 and right is 4. We 1) let left point to the right, 2) the right of the current point point to the left, and finally 3) remove left. Therefore, the nodes of the current and its children only has right node, which in this case, is 3 and 4.
     // Next step, we do the same operation but the parent of the current node until the root node.
    class Solution {
    public:
        void flatten(TreeNode* root) {
            TreeNode *dummy = root;
            helper(dummy);
        }
        void helper(TreeNode* root) {
            if (!root || !root->left && !root->right) return;
            else {
                if (root->right) {
                    helper(root->right);
                }
                if (root->left) {
                    helper(root->left);
                    TreeNode *dummy = root->left;
                    while (dummy->right) {
                        dummy = dummy->right;
                    }
                    dummy->right = root->right;
                    root->right = root->left;
                    root->left = NULL;
                }
            }
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.