[leetcode] Flatten Binary Tree to Linked List

유의할점

O(1) ?

풀이

flatten(TreeNode* root) 함수 : Flatten Binary Tree를 만드는 함수.

따라서 root의 왼쪽 / 오른쪽을 넣어서 root의 왼쪽과 오른쪽을 Flatten Binary Tree를 만든후 , root의 왼쪽을 root의 오른쪽에 달고 , 본래 root의 오른쪽은 새로달게된 root의 왼쪽 오른쪽 끝에 달게 된다.

코드

C++ : O(N)

/**
 * 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 {
private:
    TreeNode* prev = NULL;
public:
    void flatten(TreeNode* root) {
        if(root==NULL)
            return;
        
        flatten(root->left);
        flatten(root->right);
        
        TreeNode* left = root->left;
        TreeNode* right = root->right;
        
        root->left = NULL;
        root->right = left;
        
        TreeNode* cur = root;
        while(cur->right) cur = cur->right;
        cur->right = right;
    }
};

Java : stack

public void flatten(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stk = new Stack<TreeNode>();
        stk.push(root);
        while (!stk.isEmpty()){
            TreeNode curr = stk.pop();
            if (curr.right!=null)  
                 stk.push(curr.right);
            if (curr.left!=null)  
                 stk.push(curr.left);
            if (!stk.isEmpty()) 
                 curr.right = stk.peek();
            curr.left = null;  // dont forget this!! 
        }
    }

C++ : Non-recursive / No-stack

void flatten(TreeNode *root) {
	while (root) {
		if (root->left && root->right) {
			TreeNode* t = root->left;
			while (t->right)
				t = t->right;
			t->right = root->right;
		}
        if(root->left)
		    root->right = root->left;
		root->left = NULL;
		root = root->right;
	}
}