判断所有叶子节点是否处于同一级别的Java程序

1 简介

在此程序中，我们需要检查给定二叉树的所有叶是否都处于同一级别。

如果没有任何子节点，则称该节点为叶。在下图中，节点4、5和6是叶节点，因为它们没有任何子节点。节点4、5和6处于同一级别，即级别2。

2 算法思路

• 定义具有三个属性的Node类，即：左和右数据。在此，左代表节点的左子节点，右代表节点的右子节点。
• 创建节点时，数据将传递到该节点的data属性，并且左右都将设置为null。
• 定义另一个具有两个属性root和level的类。
  • 根表示树的根节点，并将其初始化为null。
  • 该级别将用于存储第一个遇到的叶子节点的级别。
• 它检查根是否为空，这意味着树为空。
• 如果树不为空，请遍历该树并检查其左，右子级为空的叶节点。
• CurrentLevel将跟踪正在遍历的当前水平。
• 当遇到第一个叶子节点时，将currentLevel的值存储在变量level中。
• 递归遍历所有级别，检查后续的叶节点。如果所有叶子的currentLevel等于存储在level中的值，则所有叶子处于同一级别。

3 程序实现

/**
 * 一点教程网： http://www.yiidian.com
 */
public class LeafLevel {  
  
    //Represent a node of binary tree  
    public static class Node{  
        int data;  
        Node left;  
        Node right;  
  
        public Node(int data){  
            //Assign data to the new node, set left and right children to null  
            this.data = data;  
            this.left = null;  
            this.right = null;  
            }  
        }  
  
    //Represent the root of binary tree  
    public Node root;  
  
    //It will store level of first encountered leaf  
    public static int level = 0;  
  
    public LeafLevel(){  
        root = null;  
    }  
  
    //isSameLevel() will check whether all leaves of the binary tree is at same level or not  
    public boolean isSameLevel(Node temp, int currentLevel ) {  
  
        //Check whether tree is empty  
        if(root == null){  
          System.out.println("Tree is empty");  
          return true;  
        }  
        else {  
            //Checks whether node is null  
            if(temp==null)  
                return true;  
  
            if(temp.left == null && temp.right == null) {  
                //If first leaf is encountered, set level to current level  
                if(level == 0) {  
                    level = currentLevel ;  
                    return true;  
                }  
                //Checks whether the other leaves are at same level of that of first leaf  
                else  
                   return (level == currentLevel) ;  
             }  
  
            //Checks for leaf node in left and right subtree recursively.  
            return  (isSameLevel(temp.left, currentLevel + 1) && isSameLevel(temp.right, currentLevel + 1)) ;  
         }  
    }  
  
    public static void main (String[] args) {  
  
        LeafLevel bt = new LeafLevel();  
        //Add nodes to the binary tree  
        bt.root = new Node(1);  
        bt.root.left = new Node(2);  
        bt.root.right = new Node(3);  
        bt.root.left.left = new Node(4);  
        bt.root.right.left = new Node(5);  
        bt.root.right.right = new Node(6);  
  
        //Checks whether all leaves of given binary tree is at same level  
        if(bt.isSameLevel(bt.root, 1))  
            System.out.println("All leaves are at same level");  
        else  
            System.out.println("All leaves are not at same level");  
  }  
}  

输出结果为：

All leaves are at same level