Java验证一棵树是否是完全二叉树

完全二叉树

　　若设二叉树的深度为k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k 层所有的结点都连续集中在最左边，这就是完全二叉树。

判断二叉树是否为完全二叉树。完全二叉树的定义是，前n-1层都是满的，第n层如有空缺，则是缺在右边，即第n层的最右边的节点，它的左边是满的，右边是空的。

以3层二叉树为例，以下情况为完全二叉树：

我们可以根据题意做题即可，我们可以采用分层遍历的方式，在判断一个具体的节点的时候，我们可以有如下的判断依据:
(1).如果这个节点的左子树为null，右子树不为null，则一定不是完全二叉树。
(2).如果这个节点的左右子树均为null(这个不用判断当前层或者下一层不能再出现含有左右子树的节点)，或者这个节点的左子树不为null但是右子树为null，则当前层或者下一层不能再出现含有左右子树的节点。
(3).如果当前节点的左右子树均不为null，则观察下一个节点。

public boolean isCompleteTree(TreeNode root){if(root == null){return false;}// 1. 先对树进行层序遍历// 如果这个标记为 false, 说明还是处在第一阶段// 如果这个标记为 true , 接下来的节点就不能有子树// 也就是第二阶段开始了int flg = 1;//第一阶段:1 第二阶段:2LinkedList queue = new LinkedList();queue.add(root);while(!queue.isEmpty()){TreeNode temp = queue.poll();if(flg == 1){// 合格的状态, 继续往下遍历.// 就把左右子树加入队列就行了if(temp.left != null && temp.right != null){queue.offer(temp.left);queue.offer(temp.right);}else if(temp.left == null && temp.right != null){// 这种情况铁定不是完全二叉树return false;}else if(temp.left != null && temp.right == null){// 这是临界状态, 开启第二阶段queue.offer(temp.left);//开启第二阶段flg = 2;}else{// 左右子树都为空, 开启第二阶段flg = 2;}}else{//开启第二阶段// 第二阶段要求节点必须没有子树. 只要子树存在, 就不是完全二叉树if(temp.left != null || temp.right != null){return false;}}}return true;}

.如果这个节点的左右子树均为null(这个不用判断当前层或者下一层不能再出现含有左右子树的节点)的写法:

这样更易于理解: 

import java.util.*;/** public class TreeNode {*   int val = 0;*   TreeNode left = null;*   TreeNode right = null;* }*/public class Solution {//是否是儿茶搜索树boolean isTwoSearchFlg = true;/*** * @param root TreeNode类 the root* @return bool布尔型一维数组*/public boolean[] judgeIt (TreeNode root) {boolean[] result = new boolean[2];istwoSearchTree(root);result[0] = isTwoSearchFlg;result[1] = isFullTree(root);return result;}int preTreeNodeVal = Integer.MIN_VALUE;public void istwoSearchTree(TreeNode root){if(root == null || !isTwoSearchFlg){return;}istwoSearchTree(root.left);if(root.val > preTreeNodeVal){preTreeNodeVal = root.val;}else{isTwoSearchFlg = false;return;}istwoSearchTree(root.right);}public boolean isFullTree(TreeNode root){if(root == null){return false;}int condition = 1;LinkedList queue = new LinkedList();queue.offer(root);while(!queue.isEmpty()){TreeNode temp = queue.poll();if(1 == condition){if(temp.left!=null && temp.right!=null){queue.offer(temp.left);queue.offer(temp.right);}else if(temp.left == null && temp.right != null){return false;}else if(temp.left!=null && temp.right == null){condition = 2;queue.offer(temp.left);}}else{if(temp.left!=null || temp.right != null){return false;}}}return true;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！