두 갈래 나무--깊이

두 갈래 나무에서 가장 흔히 볼 수 있는 것은 한 그루의 나무의 깊이를 구하는 것이다. 즉, 나무에서 뿌리 노드에서 잎 노드까지의 경로 중 가장 긴 것은 가장 흔히 볼 수 있는 방식은 귀속구해와 비귀속구해로 나뉘는데 구체적인 코드는 다음과 같다.나무구조

public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

차례로 돌아가며 해답을 구하다.

public int maxDepth(TreeNode root){
    if(root == null)
        return 0;
    return Math.max(maxDepth(root.right), maxDepth(root.left))+1;
}

비귀속 구해

public int maxDepth(TreeNode root){
        if(root == null)
            return 0;
        Deque<TreeNode> stackTree = new LinkedList<>();
        Deque<Integer> stackNum = new LinkedList<>();
        int maxDepth = 0;
        stackTree.push(root);
        stackNum.push(1);
        while(!stackTree.isEmpty()){
            TreeNode curNode = stackTree.pop();
            int curDepth = stackNum.pop();

            maxDepth = Math.max(maxDepth, curDepth);
            if(curNode.left != null){
                stackTree.push(curNode.left);
                stackNum.push(curDepth+1);
            }

            if(curNode.right != null){
                stackTree.push(curNode.right);
                stackNum.push(curDepth+1);
            }
        }

        return maxDepth;
    }