Two easy to understand C++ pre-order traversal solution (recursive and iterative) with demo


  • 1

    Recursive solution

    class Solution {
    private:
        TreeNode* pre = NULL;
        
    public:
        void flatten(TreeNode* root) {
            if(!root) return;
            pre = root;
            
            TreeNode* right = root->right;
            if(root->left) root->right = root->left;
            flatten(root->left);
            pre->right = right;
            flatten(root->right);
            
            root->left = NULL;
        }
    };
    

    Iterative solution: Starting from parent node runner, keep a copy of right child, let it be right first since we are going to reset runner->right: if runner has left child(runner->left), it will become the new right child of runner, and then we set left child to nullptr. How to deal the old right child right? We need to find it a new parent, which should be the rightmost node in the subtree rooted at the old left child, which we just set as the new right child(runner->right), so rRunner is doing this work to find the new parent for right. After all of this, we continue with runner's right child.

    current runner: 1
    
    before update:
         1
        / \
       2   5
      / \   \
     3   4   6
    
    update:
    right = 1->right = 5
    1->right = 2
    rRunner = 4
    4->right = right = 5
    
    after update:   
         1
          \
           2   
          / \   
         3   4   
              \
               5
                \
                 6
    
    next runner: 2
    

    Code

    class Solution {
    public:
        void flatten(TreeNode* root) {
            TreeNode* runner = root;
            
            while(runner){
                if(runner->left){
                    TreeNode* right = runner->right;
                    runner->right = runner->left;
                    runner->left = nullptr;
                    runner = runner->right;
                    
                    TreeNode* rRunner = runner;             
                    while(rRunner->right){
                        rRunner = rRunner->right;
                    }                   
                    rRunner->right = right;  /*rRunner is the new parent of `right`*/
                }else{
                    runner = runner->right;    
                }         
            }
        }
    };

Log in to reply
 

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