二叉树层次遍历，深度计算(递归+非递归)

Dear 丶 2022-03-29 13:08 205阅读 0赞

import java.util.LinkedList;
    import java.util.List;
    
    public class BinaryTreeDeep {
        public static void main(String[] args){
            Tree tree1=new Tree("1");
            Tree tree2=new Tree("2");
            Tree tree3=new Tree("3");
            Tree tree4=new Tree("4");
            Tree tree5=new Tree("5");
            Tree tree7=new Tree("7");
            Tree tree8=new Tree("8");
            Tree tree9=new Tree("9");
            Tree tree10=new Tree("10");
    
            tree1.setLeft(tree2);
            tree1.setRight(tree3);
            tree2.setLeft(tree4);
            tree3.setRight(tree5);
            tree5.setLeft(tree7);
            tree7.setLeft(tree8);
            tree8.setRight(tree9);
            tree4.setRight(tree10);
    
            /*
                   1
                 2    3
               4         5
                 10         7
                          8
                              9
             */
    
            int deep=getDeep(tree1);
            System.out.println("深度(递归)是"+deep);
    
            int deep1=getDeep1(tree1);
            System.out.println("深度(非递归)是"+deep1);
    
            System.out.println("层次遍历是：");
            levelTraversal(tree1);
        }
    
        private static int getDeep(Tree root){
    
            if(null==root){
                return 0;
            }
    
            if(null==root.getLeft()&&null==root.getRight()){
                return 1; //如果只有他自己就是1
            }
    
            int left=0;
            int right=0;
            if(null!=root.getLeft()){
                left=getDeep(root.getLeft());
            }
            if(null!=root.getRight()){
                right=getDeep(root.getRight());
            }
            int deep=Math.max(left,right)+1;
            return deep;
        }
    
        private static int getDeep1(Tree root){
            if(null==root){
                return 0;
            }
    
            List<Tree> nodes=new LinkedList<>();
            ((LinkedList<Tree>) nodes).offer(root);
            int current=0;
            int deep=0;
            int levelNodeSize=0;
            while(nodes.size()>0){
                levelNodeSize=nodes.size();//当前层节点的个数
                current=0;
                while(current<levelNodeSize){
                    Tree tmp=((LinkedList<Tree>) nodes).poll();
                    if(null!=tmp.getLeft()){
                        ((LinkedList<Tree>) nodes).offer(tmp.getLeft());
                    }
    
                    if(null!=tmp.getRight()){
                        ((LinkedList<Tree>) nodes).offer(tmp.getRight());
                    }
    
                    current++;
                }
    
                deep++;
            }
    
            return deep;
        }
    
        private static void levelTraversal(Tree root){
            List<Tree> nodes=new LinkedList<>();
            ((LinkedList<Tree>) nodes).offer(root);
            while(!nodes.isEmpty()){
                Tree tmp=((LinkedList<Tree>) nodes).poll();
                System.out.print(tmp.getRoot()+" ");
                if(null!=tmp.getLeft()){
                    ((LinkedList<Tree>) nodes).offer(tmp.getLeft());
                }
    
                if(null!=tmp.getRight()){
                    ((LinkedList<Tree>) nodes).offer(tmp.getRight());
                }
            }
            System.out.println("");
        }
    }
    
    class Tree{
        private String root;
        private Tree left;
        private Tree right;
    
        public Tree(String root) {
            this.root = root;
        }
    
        public String getRoot() {
            return root;
        }
    
        public void setRoot(String root) {
            this.root = root;
        }
    
        public Tree getLeft() {
            return left;
        }
    
        public void setLeft(Tree left) {
            this.left = left;
        }
    
        public Tree getRight() {
            return right;
        }
    
        public void setRight(Tree right) {
            this.right = right;
        }
    
    
    }