114.-flatten-binary-tree-to-linked-list.md

114. Flatten Binary Tree to Linked List

{% tabs %} {% tab title="GO" %}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func flatten(root *TreeNode)  {
    curr := root
    for curr!=nil {
        if curr.Left!=nil{
            tmp := curr.Left
            for tmp.Right!=nil {
                tmp = tmp.Right
            }
            tmp.Right = curr.Right
            curr.Right = curr.Left
            curr.Left = nil
        }
        curr = curr.Right
    }
}

{% endtab %}

{% tab title="C++" %}

/**
 * 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) {`
        if (!root) {
            return;
        }
        if (root->left) {
            flatten(root->left);
        }
        if (root->right){
            flatten(root->right);
        }
        
        TreeNode *tmp;
        tmp = root->right;
        root->right = root->left;
        root->left= NULL;
        
        while (root->right) {
            root = root->right;
        }
        root->right = tmp;
        
    }
};

{% endtab %}

{% tab title="recursive" %}

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        ### 统一node.right 就是 node.next
        ## 先用recursion 来做

        def t(root):
            if not root:
                return None
            vals.append(root)
            t(root.left)
            t(root.right)

        vals = []
        t(root) ## 这个我们就用递归把它们存下来了
        for i in range(len(vals) - 1):
            vals[i].left = None
            vals[i].right = vals[i+1]

class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        ### 统一node.right 就是 node.next
        ## 先用recursion 来做

        ## 先思考就是三个nodes 时的状态, 永远是root第一 left 次之,right last 
        # root.left.right = root.right
        # root.right = root.left

        ### 右 左 根  
        ### 右>左>根

        self.pre = None
        def t(root):
            if not root:
                return None 
            t(root.right) ## 会先执行一直往右
            t(root.left)
            root.left = None # 断开 
            #　print(self.pre)
            root.right = self.pre
            self.pre = root
        t(root)

{% endtab %}

{% tab title="iterative" %}

class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        ### 　   完全不递归 
        ### 那要用什么装root呢?
        stack = []
        stack.append(root)
        head = TreeNode(0)
        while stack:
            node = stack.pop()
            if not node:
                continue
            stack.append(node.right)
            stack.append(node.left) ## 后进先出
            head.right = node
            head.left = None
            head = node # 换下一个

{% endtab %} {% endtabs %}