全民建网站,中建八局第一建设有限公司税号,株洲市网站建设,重庆那些公司的网站是网易做的文章目录题目描述思路 代码层级遍历法BFS二刷题目描述
考察对完全二叉树性质的理解
思路 代码
层级遍历法
一开始试了自底向上的DFS#xff0c;过了90%的用例#xff0c;还是考虑得不够全 层级遍历#xff1a;代码比较多#xff0c;但是总体效…
文章目录题目描述思路 代码层级遍历法BFS二刷题目描述
考察对完全二叉树性质的理解
思路 代码
层级遍历法
一开始试了自底向上的DFS过了90%的用例还是考虑得不够全 层级遍历代码比较多但是总体效率和方法2差不多
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {DequeTreeNode queue new ArrayDeque();public boolean isCompleteTree(TreeNode root) {queue.offer(root);return bfs(1, 1);}public boolean bfs(int nodeNums, int except) {if(queue.size() 0) {return true;}int counts 0;boolean flag false;for(int i 0; i nodeNums; i) {TreeNode tempNode queue.pop();if(tempNode.left ! null) {if(flag) {return false;}queue.offer(tempNode.left);counts;}else {flag true;}if(tempNode.right ! null) {if(flag) {return false;}queue.offer(tempNode.right);counts;}else {flag true;}}if(nodeNums ! except !queue.isEmpty()) {return false;}return bfs(counts, 2 * except);}
}BFS
注意要使用能存储 null 值的集合类比如 ArrayDeque 就不行核心思路当前节点为空时如果后面包括右边、下面有节点则不是完全二叉树。
class Solution {// 完全二叉树判断当前节点为空时后面包括右边、下面不能有节点public boolean isCompleteTree(TreeNode root) {LinkedListTreeNode queue new LinkedList();queue.offer(root);for(TreeNode cur queue.poll(); cur ! null; cur queue.poll()) {queue.offer(cur.left);queue.offer(cur.right);}// 如果之后还有非空元素说明不是完全二叉树while(!queue.isEmpty()) {if(queue.poll() ! null) {return false;}}return true;}
}二刷
class Solution {public boolean isCompleteTree(TreeNode root) {// jojo的奇妙做法。。不知道怎么想的反正 A 了问题不大ListTreeNode list new LinkedList();QueueTreeNode queue new ArrayDeque();queue.offer(root);list.add(root);while(!queue.isEmpty()) {TreeNode temp queue.poll();list.add(temp.left);list.add(temp.right);if(temp.left ! null) {queue.offer(temp.left);}if(temp.right ! null) {queue.offer(temp.right);}}boolean flag false;for(TreeNode temp : list) {if(temp null) {flag true;} else if (flag) {return false;}}return true;}
}简单写法八行代码光速解决
class Solution {public boolean isCompleteTree(TreeNode root) {LinkedListTreeNode queue new LinkedList();for(TreeNode cur root; cur ! null; cur queue.poll()) {queue.offer(cur.left);queue.offer(cur.right);}while(!queue.isEmpty()) {if(queue.poll() ! null) {return false;}}return true;}
}
