4월 1-2주차 알고리즘 (2)

[EJSohn]

Binary Tree 레벨별로 분류하기 - 거꾸로

Binary Tree가 주어졌을 때 leaf에서 root까지의 값을 레벨별로 거꾸로 저장한 배열을 반환하시요 (순서는 왼쪽에서 오른쪽으로입니다)

Example: Binary Tree [3,9,20,null,null,15,7] 가 주어졌을 때,

    3
   / \
  9  20
    /  \
   15   7

다음의 배열을 반환합니다.

[
  [15,7],
  [9,20],
  [3]
]

Input TreeNode 클래스의 root 변수가 입력으로 들어옵니다

class TreeNode {
  int val
  *TreeNode left
  *TreeNode right
}

[kyunooh]

이야 트리 한땀한땀 장인 정신으로 적었네 ㅋㅋㅋㅋ

[su-apollo]

https://ideone.com/Cnw1Up

[kyunooh]

package org.sundaybird;

import java.util.*;
import java.lang.*;

class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val) {
        this.val = val;
    }
}

public class TreeTree {
    public static void main (String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        List<List<Integer>> answer = new ArrayList<>();
        insertStack(answer, root);
        answer.add(Collections.singletonList(root.val));
        System.out.println(answer);

    }

    public static void insertStack(List<List<Integer>>  answer, TreeNode node) {
        List<Integer> l = new ArrayList<>();
        if(node.left != null) {
            l.add(node.left.val);
            insertStack(answer, node.left);
        }
        if(node.right != null) {
            l.add(node.right.val);
            insertStack(answer, node.right);
        }

        if(node.left != null && node.right != null)
            answer.add(l);
    }
}

[kyunooh]

시청자 분께서 반례를 던져주셨기에 코드를 수정한다!

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val) {
        this.val = val;
    }
}

class Ideone {
    public static void main (String[] args) throws java.lang.Exception {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        //root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        List<List<Integer>> answer = new ArrayList<>();
        insertStack(answer, root);
        answer.add(Collections.singletonList(root.val));
        System.out.println(answer);

    }

    public static void insertStack(List<List<Integer>>  answer, TreeNode node) {
        List<Integer> l = new ArrayList<>();
        if(node.left != null) {
            l.add(node.left.val);
            insertStack(answer, node.left);
        }
        if(node.right != null) {
            l.add(node.right.val);
            insertStack(answer, node.right);
        }

        if(node.left != null || node.right != null)
            answer.add(l);
    }
}

[kyunooh]

반례를 해결했는데 찜찜하다 이맬이야...

package org.sundaybird;

import java.util.*;
import java.lang.*;

class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val) {
        this.val = val;
    }
}

public class TreeTree {
    public static void main (String[] args) {
        if(!"[[15, 7], [9, 20], [3]]".equals(test1())) {
            System.out.println("test1 failed!! :: " + test1());
        }

        if(!"[[7], [9, 20], [3]]".equals(test2())) {
            System.out.println("test2 failed!! :: " + test2());
        }

        if(!"[[5, 6, 15, 7], [9, 20], [3]]".equals(test3())) {
            System.out.println("test3 failed!! :: " + test3());
        }
    }

    public static String getString(TreeNode t) {
        List<List<Integer>> answer = new ArrayList<>();
        insertStack(answer, t);
        Collections.reverse(answer);
        return answer.toString();
    }

    public static String test1() {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        return getString(root);
    }

    public static String test2() {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        //root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        return getString(root);
    }

    public static String test3() {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.left.left = new TreeNode(5);
        root.left.right = new TreeNode(6);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        return getString(root);
    }

    public static void insertStack(List<List<Integer>> answer, TreeNode node) {
        insertStack(answer, node, 0);
    }

    public static void insertStack(List<List<Integer>> answer, TreeNode node, int depth) {
        if(answer.size() == depth) {
            answer.add(new ArrayList<>());
        }
        answer.get(depth).add(node.val);

        if(node.left != null) {
            insertStack(answer, node.left, depth + 1);
        }

        if(node.right != null) {
            insertStack(answer, node.right, depth + 1);
        }
    }

}

[joshuakimDwan]

from typing import Optional

class TreeNode:
    def __init__(self, val, left: Optional['TreeNode'] = None, right: Optional['TreeNode'] = None):
        self.val = val
        self.left = left
        self.right = right

    def __str__(self):
        return str(self.val)

    # 무쓸모 코드지만 오랜만에 생각이 나서,,,
    @staticmethod
    def traverse(node: 'TreeNode'):
        if not node:
            return
        TreeNode.traverse(node.left)
        print(node.val)
        TreeNode.traverse(node.right)

def reverse_btree(node: TreeNode):
    result = list()
    nodes = [node]
    next_nodes = []
    while len(nodes) > 0:
        result.insert(0, [n.val for n in nodes])
        for n in nodes:
            if n.left:
                next_nodes.append(n.left)
            if n.right:
                next_nodes.append(n.right)
        nodes = next_nodes
        next_nodes = []
    return result

if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.right = TreeNode(20)
    root.right.left = TreeNode(15)
    root.right.right = TreeNode(7)
    assert reverse_btree(root) == [[15, 7], [9, 20], [3]]

[EJSohn]

컴파일은 이쪽에서: https://leetcode.com/problems/binary-tree-level-order-traversal-ii/