<Medium> Flatten Binary Tree to Linked List (LeetCode : C#)

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

📕 문제 설명

이진 트리의 root가 주어질 때 연결 리스트로 flatten하여 반환

1) 연결 리스트는 동일한 TreeNode 클래스를 사용하여 반환하며 왼쪽 자식 포인터는 null로, 오른쪽 자식 포인터에 값을 저장한다.
2) 연결 리스트는 이진 트리의 pre-order 순회 순서와 동일함

• Input
  이진 트리의 root
• Output
  flatten된 연결 리스트

예제

풀이

단순 preorder 구현 문제이다.
stack을 써서 root -> 왼쪽 -> 오른쪽 순서니까 root 제일 처음에 처리하고 넣을 때는 right -> left 로 넣어서 left가 먼저 뽑힐 수 있게 해야한다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public void Flatten(TreeNode root) {

        if (root == null) return;

        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.Push(root);

        TreeNode answerNode = null;

        while (stack.Count >= 1)
        {
            TreeNode node = stack.Pop();
            if (node.right != null) stack.Push(node.right);
            if (node.left != null) stack.Push(node.left);

            if (answerNode == null) answerNode = node;
            else
            {
                answerNode.right = new TreeNode(node.val);
                answerNode = answerNode.right;
            }

            answerNode.left = null;
        }
    }
}

결과