如何知道二叉树的深度？

Answer 1

考察点：二叉树

 

实现二叉树的深度方式有两种，递归以及非递归。

①递归实现：

为了求树的深度，可以先求其左子树的深度和右子树的深度，可以用递归实现，递归的出口就是节点为空。返回值为0；

②非递归实现：

利用层次遍历的算法，设置变量level记录当前节点所在的层数，设置变量last指向当前层的最后一个节点，当处理完当前层的最后一个节点，让level指向+1操作。设置变量cur记录当前层已经访问的节点的个数，当cur等于last时，表示该层访问结束。

层次遍历在求树的宽度、输出某一层节点，某一层节点个数，每一层节点个数都可以采取类似的算法。

树的宽度：在树的深度算法基础上，加一个记录访问过的层节点个数最多的变量max,在访问每层前max与last比较，如果max比较大，max不变，如果max小于last，把last赋值给max;

代码解释：

import java.util.ArrayList;
import java.util.Scanner;
public class Main
{
    // 定义节点
    class Node{
        int val;
        Nodeleft;
        Node right;
        public Node(int val) {
            this.val = val;
        }
    }
    
    public ArrayList<Integer> gzy; // 保存根左右的序列
    public ArrayList<Integer> zgy; // 保存左跟右的序列
    public ArrayList<Node> pack;       // 保存已经排好的节点
    
    public static void main(String[] args) {
        Main main = new Main();
        main.getResult();
        
    }
    
    public void getResult() {
        //init Scanner
		scanner = new Scanner(System.in);
        int count = scanner.nextInt();
        gzy = new ArrayList<>();
        zgy = new ArrayList<>();
        for(int i = 0; i < count; i++) {
            gzy.add(scanner.nextInt());
        }
        for(int j = 0; j < count; j++) {
            zgy.add(scanner.nextInt());
        }
        pack= new ArrayList<>();       // 已经还原的节点
        
        //exception
        if(count== 1) {
            System.out.println(gzy.get(0));
            return;
        }
        // 构造最左侧节点的二叉树
        Node node = new Node(gzy.get(0));
        pack.add(node);
        int index1 = 1;     // 根左右的下标
        Node tmp = node;
        while(gzy.get(index1) != zgy.get(0)) {      // 如果没访问到最左边的叶子节点,继续还原最左侧二叉树
            tmp.left = new Node(gzy.get(index1++));
            tmp = tmp.left;
            pack.add(tmp);
        }
        tmp.left = new Node(gzy.get(index1++));
        pack.add(tmp.left);
        
        // 加入剩余的节点完善二叉树
        for(int k = index1; k < gzy.size(); k++) {
            fillErCS(gzy.get(k));
        }
        
        // 层次遍历
        ArrayList<Node> res = new ArrayList<>();
        res.add(node);
        int num = 0;
        while(res.size()!= num) {
            System.out.print(res.get(num).val + "");
            if(res.get(num).left != null) {
                res.add(res.get(num).left);
            }
            if(res.get(num).right != null) {
                res.add(res.get(num).right);
            }
            num++;
        }
    }
    
    // 将值为val的节点加入二叉树
    private void fillErCS(int val) {
        int index = zgy.indexOf(val);
        // 每一个遍历的节点都是val节点的根或者在其左边
        for(int i = index-1; i >= 0; i--) {
            if(findNode(zgy.get(i)) != null) {  // 找到待插入节点的根节点或者其左边的节点
                Node node = findNode(zgy.get(i));
                insert(node,val);
                break;
            }      
        }
    }
    
    // 将节点val插入二叉树
    private void insert(Node node, int val) {
        if(zgy.indexOf(node.val)> zgy.indexOf(val)) {  // node在待插入节点的右边
            if(node.left == null) {
                node.left= new Node(val);
                pack.add(node.left);
                return;
            }
            insert(node.left, val);
        }
        else
		{     
            //node在待插入节点的左边或是其根
            if(node.right == null) {
                node.right= new Node(val);
                pack.add(node.right);
                return;
            }
            insert(node.right, val);
        }
    }
    // 根据val找到pack里的节点
    private Node findNode(int val) {
        for(Node node : pack) { 
            if(node.val == val) {
                return node;
            }
        }
        return null;
    }
}