欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

打遍天下二叉树

程序员文章站 2022-03-19 16:10:19
文章目录1. 基本概念2. 深度优先遍历2.1 递归方式2.2 非递归方式3. 广度优先遍历4. 案例4.1 二叉树的最大深度4.2 记录每一层的所有元素在做一些二叉树的过程中,我发现,大多数题目是有规律可循的.所以打算总结一下二叉树这一块的打法.ps: 文中的所有代码均可在 https://github.com/xfhy/Algorithms 中找到. 该项目有一些关于二叉树的基本学习代码和二叉树的题解等.1. 基本概念二叉树(binary tree) 是树的一种特殊形式。二叉,顾名思义,这...


在做一些二叉树的过程中,我发现,大多数题目是有规律可循的.所以打算总结一下二叉树这一块的打法.

ps: 文中的所有代码均可在 https://github.com/xfhy/Algorithms 中找到. 该项目有一些关于二叉树的基本学习代码和二叉树的题解等.

我的所有原创Android知识体系,已打包整理到GitHub.努力打造一系列适合初中高级工程师能够看得懂的优质文章,欢迎star~

1. 基本概念

  • 二叉树(binary tree) 是树的一种特殊形式。二叉,顾名思义,这种树的每个节点最多有2个孩子节点。注意,这里是最多有2个,也可能只有1个,或者没有孩子节点。
  • 满二叉树: 一个二叉树的所有非叶子节点都存在左右孩子,并且所有叶子节点都在同一层级上.
  • 完全二叉树: 对一个有n个节点的二叉树,按层级顺序编号,则所有节点的编号为从1到n.如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同,则这个二叉树为完全二叉树.
  • 二叉查找树(又名: 二叉排序树,二叉搜索树): 这种二叉树的主要作用就是进行查找操作.它的中序遍历是排好序了的,即由小到大. 满足二叉查找树需要几个条件
    1. 如果左子树不为空,则左子树上所有节点的值均小于根节点的值
    2. 如果右子树不为空,则右子树上所有节点的值均大于根节点的值
    3. 左右子树也都是二叉查找树
  • 从节点之间位置关系的角度来看,二叉树的遍历分为4种
    1. 前序遍历(根节点在前)
    2. 中序遍历
    3. 后序遍历
    4. 层序遍历
  • 从更宏观的角度来看,二叉树的遍历归结为两大类
    1. 深度优先遍历(前序、中序、后序遍历)
    2. 广度优先遍历(层序遍历)

文中的二叉树节点定义如下:

public static class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}

2. 深度优先遍历

2.1 递归方式

递归的方式实现深度优先遍历代码非常简洁,往往只需要几行代码即可.用递归来实现深度优先遍历是比较自然的,仅仅只是输出的执行位置不同而已.下面我们来看哈代码:

//前序遍历
public void preOrderTraveral(TreeNode node) {
    if (node == null) {
        return;
    }
    System.out.println(node.val);
    preOrderTraveral(node.left);
    preOrderTraveral(node.right);
}

//中序遍历
public void inOrderTraveral(TreeNode node) {
    if (node == null) {
        return;
    }
    inOrderTraveral(node.left);
    System.out.println(node.val);
    inOrderTraveral(node.right);
}

//后序遍历
public void postOrderTraveral(TreeNode node) {
    if (node == null) {
        return;
    }
    postOrderTraveral(node.left);
    postOrderTraveral(node.right);
    System.out.println(node.val);
}

2.2 非递归方式

绝大多数可以用递归解决的问题,都可以用栈来解决.它们都有回溯的特性.

首先来看前序遍历,实现非递归方式前序遍历的思路:

  1. 用一个栈来记录访问过的节点
  2. 然后从根节点开始往左节点遍历,一直往下,直到左边没有左节点
  3. 然后弹栈,继续访问弹出的这个元素的右节点.如果这个右节点有左子树的话,把当前节点当做根节点,继续重复2步骤
  4. 直到把所有元素都遍历完成
//前序遍历 
public void preOrderTraveralWithStack(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode treeNode = root;
    while (treeNode != null || !stack.isEmpty()) {
        //不断往栈中压入左节点,直到左边没有左节点
        while (treeNode != null) {
            System.out.println(treeNode.val);
            stack.push(treeNode);
            treeNode = treeNode.left;
        }
        //弹栈 访问右边节点
        if (!stack.isEmpty()) {
            treeNode = stack.pop();
            treeNode = treeNode.right;
        }
    }
}

然后我们来看中序遍历,在前序遍历的基础上,只需要稍等改动一下sout的位置即可.从根节点开始找二叉树的最左节点,找到最左节点后访问,对于每个节点来说,它都是以自己为根的子树的根节点,访问完之后就可以转到右儿子上了.

public void middleOrderTraversal(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode treeNode = root;
    while (treeNode != null || !stack.isEmpty()) {
        //不断往栈中压入左节点,直到左边没有左节点
        while (treeNode != null) {
            stack.push(treeNode);
            treeNode = treeNode.left;
        }
        //弹栈 访问右边节点
        if (!stack.isEmpty()) {
            treeNode = stack.pop();
            System.out.println(treeNode.val);
            treeNode = treeNode.right;
        }
    }
}

后续遍历就稍微复杂点,其实也只需要在先序遍历的基础上稍微改改就行了,先序是:中前后,改一下while中的左右压栈顺序就是: 中后前,得到数据之后再反转,即:前后中.就得到了最后的结果

public List<Integer> postOrderTraversal(TreeNode root) {
    LinkedList<Integer> res = new LinkedList<>();
    if (root == null) {
        return res;
    }
    LinkedList<TreeNode> stack = new LinkedList<>();
    stack.add(root);
    while (!stack.isEmpty()) {
        TreeNode pop = stack.pop();
        res.add(pop.val);
        if (pop.left != null) {
            stack.push(pop.left);
        }
        if (pop.right != null) {
            stack.push(pop.right);
        }
    }
    Collections.reverse(res);
    return res;
}

3. 广度优先遍历

即按照高度顺序一层一层的访问整棵树,高层次节点将会比低层次节点先被访问到.

下面来看一下用代码怎么实现二叉树的层序遍历,这里需要用到一个队列.将根节点入队,

/**
 * 二叉树层序遍历
 */
public void levelOrderTraversal(TreeNode root) {
    //1. 声明一个队列,将根节点入队
    //2. 然后将根节点出队,在根节点出队时将根节点的左节点和右节点都入队
    //3. 循环遍历队列,依次出队,在第2步中的左节点出队时,将自己视为根节点,然后将左右节点入队. 同理,右节点也一样
    //4. 遍历完队列时,所有节点的左右节点都遍历完了.
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.println(node.val);
        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
    }
}

4. 案例

4.1 二叉树的最大深度

根节点的最大深度=左节点最大深度+右节点最大深度+1

这就非常适合递归,直接递归安排.

/**
 * 二叉树的最大深度
 * 思路: 比较左子树的最大深度和右子树的最大深度,
 * 左子树的最大深度同样也适用于这种思路,右子树的最大深度同样也适用于这种思路
 * 这就很适合递归,在访问到空节点时退出.
 * 最后深度需要+1,因为需要计算上根节点.
 */
public static int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

4.2 记录每一层的所有元素

有时候我们需要记录每一层上的所有元素,这时我们可以在上面二叉树层序遍历的基础上,稍稍改进一下即可: 遍历一层的时候,先记录这层的元素个数,再依次添加到记录的集合中,顺便把这些元素的左右节点入队. 继续遍历下一层.

/**
 * 二叉树层序遍历 且记录每一层的所有元素
 *
 * @param root 二叉树根节点
 */
public List<List<TreeNode>> levelOrderTraversals(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    List<List<TreeNode>> tree = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        LinkedList<TreeNode> levels = new LinkedList<>();
        for (int i = 0; i < size; i++) {
            TreeNode poll = queue.poll();
            levels.add(poll);
            if (poll.left != null) {
                queue.offer(poll.left);
            }
            if (poll.right != null) {
                queue.offer(poll.right);
            }
        }
        tree.add(levels);
    }
    return tree;
}

本文地址:https://blog.csdn.net/xfhy_/article/details/110467034