958. Check Completeness of a Binary Tree 发表于 2022-01-18 BFS1234567891011121314151617181920212223class Solution { public boolean isCompleteTree(TreeNode root) { boolean nullNodeHasAppeared = false; Queue<TreeNode> queue = new LinkedList<>(); // 队列中包含空节点 queue.offer(root); while (!queue.isEmpty()) { TreeNode node = queue.poll(); if (node == null) { nullNodeHasAppeared = true; } else { if (nullNodeHasAppeared) { return false; } queue.offer(node.left); queue.offer(node.right); } } return true; }} DFS123456789101112131415161718192021222324252627282930class Solution { private static class ResultHolder { private boolean isComplete = true; } public boolean isCompleteTree(TreeNode root) { ResultHolder resultHolder = new ResultHolder(); Deque<Integer> pathHighQueue = new LinkedList<>(); dfs(root, resultHolder, pathHighQueue, 0); return resultHolder.isComplete; } private void dfs(TreeNode root, ResultHolder resultHolder, Deque<Integer> pathHighQueue, int high) { if (!resultHolder.isComplete) { return; } if (root == null) { if (!pathHighQueue.isEmpty() && (high > pathHighQueue.getLast() || high < pathHighQueue.getFirst() - 1)) { resultHolder.isComplete = false; return; } pathHighQueue.add(high); } else { dfs(root.left, resultHolder, pathHighQueue, high + 1); dfs(root.right, resultHolder, pathHighQueue, high + 1); } }} Reference958. Check Completeness of a Binary Tree