[알고리즘] 이진트리 binary tree DFS, BFS

코딩테스트 전, 툭 치면 툭 나와야할만한 코드 스니펫들 모음.

이진트리 클래스

public class Node {
    private Node left;
    private Node right;
    private int value;

    public Node(Node left, Node right, int value){
        this.left = left;
        this.right = right;
        this.value = value;
    }

    public Node getLeft(){
        return left;
    }
    public Node getRight(){
        return right;
    }
    public Node getValue(){
        return value;
    }
}

이진트리 DFS - preorder traversal(종주)

(inorder, postorder는 방문 순서만 바꿈)

void preorderTraversal(Node root){  
	if(root == null) return;  
	root.printValue();  
	preorderTraversal(root.getLeft());  
	preorderTraversal(root.getRight());  
}

이진트리 높이 구하기

public static int treeHeight(Node n){
    if(n == null){
        return 0;
    }
    currHeight = 1 + Math.max(treeHeight(n.getLeft()), treeHeight(n.getRight());

    return currHeight;
}

이진트리 BFS

 

 

LeetCode Sample Questions

366. Find Leaves of Binary Tree

(medium)
트리 높이 구하기 입문/전형같은 문제

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

from collections import defaultdict

class Solution:
    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:
        result_dic = collections.defaultdict(list) 
        result_list = []

        def getHeight(root):
            if root is None:
                return 0

            height = 1 + max(getHeight(root.left), getHeight(root.right))
            result_dic[height].append(root.val)
            return height

        getHeight(root)

        for i in range(1, len(result_dic) + 1):
            result_list.append(result_dic[i])

        return result_list

• time complexity:
  DFS tree traverse에 O(N)
  dict에서 list로 정렬하는데 O(tree height)
  결국 O(N)인데 dict 대신 바로 list로 넣으면 time/space에서 더 최적화가 가능할 것. 
• space complexity
  dict, list 각각 O(N)