Tree: Height of a Binary Tree 풀이 Java (Binary Tree 높이 구하기)

Tree: Height of a Binary Tree | HackerRank

 

문제

The height of a binary tree is the number of edges between the tree's root and its furthest leaf.

Binary Tree의 높이를 구해라.

 

Output Format

Your function should return a single integer denoting the height of the binary tree.

Sample Input

풀이

point 1) 각 노드별 높이를 저장하는 1차원 배열을 만든다

point 2) Stack사용 (Queue도 상관 없음)

 

재귀 사용하지 않은 이유는 Node로 주어지기 때문에 이게 더 깔끔하다고 생각함

 

	/*
    class Node 
    	int data;
    	Node left;
    	Node right;
	*/
	public static int height(Node root) {
        // Write your code here.
        int[] h = new int[21];

        Stack<Node> stack = new Stack<Node>();
        stack.add(root);

        while (!stack.isEmpty()) {
            Node node = stack.pop();

            if (node.left != null) {
                stack.add(node.left);
                h[node.left.data] = h[node.data] + 1;
            }
            if (node.right != null) {
                stack.add(node.right);
                h[node.right.data] = h[node.data] + 1;
            }
        }

        int res = 0;
        for (int i : h) {
            res = Math.max(res, i);
        }
        return res;
    }