114. Flatten Binary Tree to Linked List

problem description

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

    1
   / \
  2   5
 / \   \
3   4   6

The flattened tree should look like:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

algorithm thought

观察知道，最后所有节点全部在右边展平，我们可以每次将左子树插入到右子树，原来的右子树接在左子树最后面，重复这个操作，直到所有的右子树都展平即可

code

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

algorithm analysis

时间复杂度O(n),对于所有节点，最多访问节点两次，访问总次数是2n，所以最后时间复杂度O(n)