두 갈래 나무의 깊이와 관련된 버클 문제(104, 110, 543)

104번:
두 갈래 나무를 정해 최대 깊이를 찾아라.
두 갈래 나무의 깊이는 뿌리 노드에서 가장 먼 잎 노드까지의 가장 긴 경로의 노드 수이다.
설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다.
예: 포크 트리 지정[3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7

최대 깊이 3을 반환합니다.
분석:
제목은 가장 큰 깊이의 정의를 제시했다. 즉, 뿌리 노드에서 가장 먼 잎사귀 결점까지의 가장 긴 경로의 노드 수이다. 그러면 두루 훑어보는 것이다. 거시적인 측면에서 보면 뿌리 노드의 좌우 나무가 누구의 깊이가 가장 큰지 보고 꺼내서 뿌리 노드의 개수 1을 더하면 최종 답이다.그러면 귀속적인 방식으로 현재 뿌리 노드 아래에서 좌우 나무의 최대치를 구하고 1을 더하여 윗층으로 돌아가 최종 뿌리 노드로 돌아갈 때까지 뿌리 노드의 좌우 나무의 최대치를 선택한 다음에 1을 더하여 최종 결과를 되돌려준다.

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

이 문제는 이후 두 문제의 기초일 뿐 매우 강한 응용 의미를 가지고 다른 문제를 해결하는 데 도움을 줄 수 있다.
 
110번:
두 갈래 나무를 정해 고도의 균형을 이루는 두 갈래 나무인지 아닌지를 판단한다.본고에서 한 그루의 고도 균형 두 갈래 나무는 한 그루의 두 갈래 나무의 각 노드의 좌우 두 개의 하위 나무의 높이 차이의 절대치가 1을 초과하지 않는다고 정의한다.
예:
주어진 두 갈래 나무[3,9,20,null,null,15,7] 

    3
   / \
  9  20
    /  \
   15   7

복귀true.
주어진 두 갈래 나무[1,2,2,3,3,null,null,4,4]

      1
      / \
     2   2
    / \
   3   3
  / \
 4   4

복귀false.
분석:
관건은 전체 두 갈래 나무의 모든 노드의 좌우자 나무의 높이차의 절대치가 1보다 작은지, 아니면 고도의 균형이 아닌 두 갈래 나무, 아니면 고도의 균형이 있는 두 갈래 나무인지를 판단하는 것이다.좌우자수의 높이차가 균형이 잡힌 두 갈래 나무인지 아닌지를 판단하는 관건이라면 우리는 좌우자수의 높이를 계산해야 한다. 사실은 깊이다. 왜냐하면 전체 두 갈래 나무가 균형이 잡힌다는 것을 확보하려면 두 갈래 나무를 두루 훑어봐야 하기 때문에 위의 문제를 빌려 해결할 수 있다.두루 돌아다니면서 균형잡힌 판단이 많아졌을 뿐이야.
코드는 다음과 같습니다.

private boolean res = true;
    public boolean isBalanced(TreeNode root) {
        if (root == null){
            return true;
        }
        getDepth(root);
        return res;
    }

    private int getDepth(TreeNode root){

        if (root == null){
            return 0;
        }
        int l = getDepth(root.left);
        int r = getDepth(root.right);
        if (Math.abs(l - r) > 1){
            res = false;
        }
        return Math.max(l,r) + 1;
    }

 
543번:
두 갈래 나무를 정하려면 직경의 길이를 계산해야 한다.두 갈래 나무의 지름 길이는 두 개의 결점 경로 길이 중 최대값입니다.이 경로는 루트 끝점을 통과하거나 통과하지 않을 수도 있습니다.
예:

    　　　 1
         / \
        2   3
       / \     
      4   5 

3을 되돌려줍니다. 길이는 경로 [4, 2, 1, 3] 또는 [5, 2, 1, 3]입니다.
참고: 두 결점 사이의 경로 길이는 둘 사이의 모서리 수로 표시됩니다.
분석:
결과 경로는 두 가지만 가능하다. 하나는 뿌리 노드에서 어떤 잎 노드까지이다.하나는 한 개의 나무의 잎 노드에서 같은 뿌리의 다른 하나의 잎 노드까지다.첫 번째 상황은 뿌리 노드가 한 그루의 나무만 있을 때만 발생할 수 있다. 그렇지 않으면 두 개의 나무가 모두 존재한다면 한 개의 나무의 잎 노드에서 다른 개의 나무의 잎 노드까지의 경로 길이는 반드시 뿌리 노드에서 잎 결점까지의 경로 길이보다 크기 때문에 첫 번째 상황을 두 번째 상황의 특수한 상황으로 볼 수 있다.경로의 길이에 대해 제목은 경로의 변의 개수라고 하는데 사실 변의 개수도 경로에서 노드의 개수를 1로 줄이는 것과 같다. 그러면 각 노드의 좌우 트리의 깊이를 직접 구하여 더하면 된다. 그리고 전체적인 구성원 변수를 정의하고 더하면 그 값을 구성원 변수의 값과 비교한다. 만약에 크면 구성원 변수를 부여한다. 많은 노드가 다 지나갈 때까지.아니면 첫 번째 문제를 토대로 고쳐야 하는가.
코드는 다음과 같습니다.

int maxr = 0;
    public int diameterOfBinaryTree(TreeNode root) {

        if (root == null){
            return 0;
        }
        getDepth(root);
        return maxr;
    }

    private int getDepth(TreeNode root){

        if (root == null){
            return 0;
        }
        int l = getDepth(root.left);
        int r = getDepth(root.right);
        if ((r+l) > maxr){
            maxr = l+r;
        }
        return Math.max(l,r) + 1;
    }