Java는 두 갈래 트리의 깊이와 폭을 구합니다

이것은 흔히 볼 수 있는 두 갈래 나무에 대한 조작이다.요약:
다음과 같이 노드의 데이터 구조를 설정합니다.

class TreeNode {
    char val;
    TreeNode left = null;
    TreeNode right = null;

    TreeNode(char _val) {
        this.val = _val;
    }
}

1. 두 갈래 나무 깊이
이것은 귀속을 사용하여 각각 왼쪽 나무의 깊이, 오른쪽 나무의 깊이를 구하고 두 깊이의 비교적 큰 값 +1을 구하면 된다.

//
    public static int getMaxDepth(TreeNode root) {
        if (root == null)
            return 0;
        else {
            int left = getMaxDepth(root.left);
            int right = getMaxDepth(root.right);
            return 1 + Math.max(left, right);
        }
    }
2. 두 갈래 나무 너비
대기열을 사용하여 두 갈래 트리를 차례로 훑어보십시오.이전 레이어를 반복해서 완성한 후, 다음 레이어의 모든 노드는 대기열에 놓여 있으며, 이때 대기열의 원소 개수는 다음 레이어의 너비입니다.이런 식으로 미루어 순서대로 다음 층을 훑어보면 두 갈래 나무의 최대 너비를 구할 수 있다.

//
    public static int getMaxWidth(TreeNode root) {
        if (root == null)
            return 0;

        Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
        int maxWitdth = 1; //
        queue.add(root); //

        while (true) {
            int len = queue.size(); //
            if (len == 0)
                break;
            while (len > 0) {// ,
                TreeNode t = queue.poll();
                len--;
                if (t.left != null)
                    queue.add(t.left); //
                if (t.right != null)
                    queue.add(t.right);//
            }
            maxWitdth = Math.max(maxWitdth, queue.size());
        }
        return maxWitdth;
    }

좋은 웹페이지 즐겨찾기