思路:完全二叉树:若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。
我们采用队列来存储这颗完全二叉树。通过bfs存储队列时候会发现,一棵正确的完全二叉树再存入的过程中一定是每一个位置都存入了一个Node节点,直到最后一个存在的点存储结束,我们的队列里面会出现如下形式:
(节点,节点,节点....节点,null,null,null.....)
所以我们不断的存储节点,直到从队列中获取到的元素是null的时候停止存储。
之后我们将剩余的存储在队列中的null节点全部抛出,如果结束时队列为空,则表示存储的树一定是完全二叉树,否则不是!
解题模板:class solution{ public static boolean judge(TreeNode root){ Queueq=new linkedList<>(); q.add(root); // 存储过程,存储时出现null节点则暂停存储! while(q.peek()!=null){ TreeNode temp=q.poll(); q.add(temp.left); q.add(temp.right); } while(!q.isEmpty()&&q.peek()==null){ q.poll();//按照正常流程,队列中由于上面步骤,此时队列中只剩下null节点全部抛出则为完全二叉树! //如果出现了其他非null节点,则说面此树一定不是完全二叉树! } if(q.isEmpty()==true)return true; else return false; } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)