二叉树的层次遍历、二叉树的生成、求深度、统计节点数

概述

在上次基本遍历后，总结一下二叉树的层次遍历、二叉树的生成、求节点深度、统计节点数，二叉树的结构定义为：

//Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

层次遍历

使用队列进行层次遍历，先将节点入列，访问节点时出列，并将子节点入列，循环至队列为空，则遍历结束。

public void levelOrder(TreeNode root) {
    if (root == null) {  // 边界判断
        return ;
    }
    Deque<TreeNode> que = new LinkedList<>();  // 队列
    TreeNode node;  // 将要访问的节点变量
    que.addLast(root);  // 先保存根节点

    while(!que.isEmpty()) {
        node = que.removeFirst();
        if(node.left != null) {  // 左子节点不为空则入列
            que.addLast(node.left);
        }
        if(node.right != null) {  // 右子节点不为空则入列
            que.addLast(node.right);
        }
        System.out.println(node.val);  // 访问当前节点
    }
}

二叉树的生成

用Scanner接收输入，节点用空格“ ”分离，”#”代表空节点，利用前序遍历生成二叉树。

public void createTree(Scanner scanner， TreeNode root) {
    String val = scanner.next();
    if (val.equals("#")) {  // #置空
        root = null;
    } else {
        root = new TreeNode();
        root.val = Integer.valueOf(val);
        createTree(scanner, root.left);  // 递归生成左右子树
        createTree(scanner, root.right);
    }
}

求节点深度

递归求深度，返回最大子节点深度加一，子节点为空则返回0。

private static int depthOfNode(TreeNode parent) {
    if (parent == null) {
        return 0;
    }
    int lDepth = depthOfNode(parent.left);
    int rDepth = depthOfNode(parent.right);
    return lDepth > rDepth ? lDepth + 1 : rDepth + 1;  // 返回较大子树深度+1
}

统计节点数

与求节点深度类似，递归求解，返回子节点数和+1，子节点为空则返回0。

private static int countOfNodes(TreeNode parent) {
    if (parent == null) {
        return 0;
    }
    int lCount = countOfNodes(parent.left);
    int rCount = countOfNodes(parent.right);
    return lCount + rCount + 1;  // 返回子树节点数和+1
}