当前位置： 首页 > news >正文

二叉树的操作及常见面试题

news 来源：原创 2024/11/20 0:29:10

文章目录

  • 前言
  • 一、四种遍历方式
  • 二、二叉树的基本操作
      • 2.1 统计二叉树的结点个数
      • 2.2 统计二叉树的叶子结点个数
      • 2.3 求二叉树第K层节点个数
      • 2.4 求二叉树的高度
      • 2.5 判断一棵树中是否包含指定的值
  • 三、二叉树的基础面试题
      • 3.1 相同的树
      • 3.2 另一棵树的子树
      • 3.3 平衡二叉树
  • 总结

前言

上一篇博主归纳了一下二叉树的基本概念以及性质：

二叉树的概念及性质

本文将附上博主自己手动实现的二叉树常见的各种操作以及归纳总结一下常见的基础面试题。

一、四种遍历方式

二叉树额所有问题最终都是四种遍历方式的衍生问题。

前、中、后序遍历为深度优先遍历（DFS），借助“栈”结构

如图：

在这里插入图片描述
1.前序遍历：

ABDEGHCF

先访问根节点，然后递归访问左子树，再递归访问右子树，根左右

递归写法：

public class PreorderTraversal {
    List<Integer> ret = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root==null){
            return ret;
        }
        ret.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return ret;
    }
}

迭代写法：

public class Preorder {
    List<Integer> list = new ArrayList<>();
    Deque<TreeNode> stack = new LinkedList<>(); //借助辅助栈
    public List<Integer> preorder(TreeNode root) {
        if (root == null){
            return list;
        }
        TreeNode cur = root;
        while (!stack.isEmpty() || cur!=null){  //右边这个条件是防止弹出根节点后，右子树还有结点的情况
            while (cur!=null){
                stack.push(cur);
                list.add(cur.val);
                cur = cur.left;
            }
            // 走到这里的时候左子树已经走到了最左下，该弹出最坐下结点，开始访问右子树了
            cur=stack.pop();
            cur = cur.right;
        }

        return list;
    }
}

2.中序遍历：

DBGHEACF

先递归左子树，再根，最后递归右子树，左根右 => 先一路向左走到根儿~’

递归写法：

public class InorderTraversal {
    List<Integer> ret = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root==null) {
            return ret;
        }
        inorderTraversal(root.left);
        ret.add(root.val);
        inorderTraversal(root.right);
        return ret;
    }
}

迭代写法：

public class InorderTraversal {
    public List<Integer> inorder(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        if (root == null){
            return list;
        }
        TreeNode cur = root;
        while (!stack.isEmpty() || cur!=null){
            while (cur!=null){
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            list.add(cur.val);
            cur = cur.right;
        }
        return list;
    }
}

3.后序遍历：

DHGEBFCA

先递归左子树再递归右子树，最后根先一路向左走到根儿~~

递归写法：

public class PostorderTraversal {
    List<Integer> ret=new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if (root==null){
            return ret;
        }
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        ret.add(root.val);
        return ret;
    }
}

迭代写法：

public class Postorder {
    public List<Integer> postorder(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }

        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode prev = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            /**
             * 前面都一样走到最左边，后面加个if判断：每次弹栈就判断当前结点是否应该处理结束，若右子树为空或者右子树处理过了，那就处理当前
             */
            if (root.right == null || root.right == prev) {
                res.add(root.val); //当前root结点就是已经处理结束的结点
                prev = root; //所以 prev指向了最新的处理结束的结点，以前的不管了反正都结束了
                root = null;
            } else {  //否则，把当前结点压回栈中
                stack.push(root);
                root = root.right;
            }
        }
        return res;
    }
}

层序遍历为广度优先遍历（BFS），借助队列结构

4.层序遍历：

从二叉树的第一层开始一层层向下遍历，每一层由左至右开始遍历

ABCDEFGH

 public void levelOrder(TreeNode<E> root) {
        Deque<TreeNode<E>> queue = new LinkedList<>();
        queue.offer(root);
        // 循环的终止条件就是队列为空
        while (!queue.isEmpty()) {
            // 取出当前层的节点个数，每当进行下一次遍历的时候，队列中就存储了该层的所有元素
            int n = queue.size();
            for (int i = 0; i < n; i++) {
                TreeNode<E> node = queue.poll();
                System.out.print(node.val + " ");
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
    }

递归把握语义，巧妙使用递归函数的作用帮助我们辅助解决问题。

注意事项：

1.先序遍历的第一个结果一定是当前二叉树的根节点
2.中序遍历左子树的结果一定再根节点左侧，右子树的遍历结果在根节点右侧
3.后序遍历的最后一个结果是当前二叉树的根节点，将后序遍历的结果集reverse得到一个先序遍历的镜像结果集 “根右左”

二、二叉树的基本操作

2.1 统计二叉树的结点个数

在这里插入图片描述

递归：

public int getNodes(TreeNode<?> root) {
        return root == null ? 0 : 1 + getNodes(root.left) + getNodes(root.right);
    }

非递归：

public int getNodesNonRecursion(TreeNode<?> root) {
        if (root == null) {
            return 0;
        }
        Deque<TreeNode<?>> queue = new LinkedList<>();
        queue.offer(root);
        int num = 0;
        while (!queue.isEmpty()) {
            TreeNode temp = queue.poll();
            num++;
            if (temp.left != null) {
                queue.offer(temp.left);
            }
            if (temp.right != null) {
                queue.offer(temp.right);
            }
        }
        return num;
    }

2.2 统计二叉树的叶子结点个数

总叶子结点个数 = 左树中的叶子结点个数 + 右树中的叶子结点个数

代码如下：

public int getLeafNodes(TreeNode<?> root) {
        // 1.边界
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            // 只有root,root就是一个叶子结点
            return 1;
        }
        // 此时root不为空，也有子树，总叶子结点个数 = 左树中的叶子结点个数 + 右树中的叶子结点个数
        return getLeafNodes(root.left) + getLeafNodes(root.right);
    }

2.3 求二叉树第K层节点个数

求以root为根的第k层结点个数 = 以root.left为根的第k - 1层结点个数 + 以root.right为根的第k - 1层结点个数

在这里插入图片描述
代码如下：

 /**
     * 传入一颗以root为根的二叉树，就能求出第k层的节点个数 k <= height(root)
     *
     * @return
     */
    public int getKLevelNodes(TreeNode root, int k) {
        // 1.边界条件
        if (root == null || k <= 0) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        // 求以root为根的第k层结点个数 = 以root.left为根的第k - 1层结点个数 + 以root.right为根的第k - 1层结点个数
        return getKLevelNodes(root.left, k - 1) + getKLevelNodes(root.right, k - 1);
    }

2.4 求二叉树的高度

当前树高等于1+左右子树中的最大树高

在这里插入图片描述代码如下：

/**
     * 传入一颗以root为根的二叉树，就能求出该树的高度是多少
     *
     * @param root
     * @return
     */
    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(height(root.left), height(root.right));
    }

2.5 判断一棵树中是否包含指定的值

代码如下：

/**
     * 判断以root为根的二叉树中是否包含指定值val
     *
     * @param root
     * @param val
     * @return
     */
    public boolean contains(TreeNode<E> root, E val) {
        if (root == null) {
            return false;
        }
        if (root.val.equals(val)) {
            return true;
        }
        // 继续在左子树和右子树中寻找是否包含指定值
        return contains(root.left, val) || contains(root.right, val);
    }

三、二叉树的基础面试题

3.1 相同的树

在这里插入图片描述思路：

相同的树就是当前结点相同并且其左右子树的结点也相同，递归实现十分容易。

代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
   public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p==null){
            if (q==null){return true;}
            return false;
        }
        if (q==null){
            if (p==null){return true;}
            return false;
        }
        if (p.val== q.val){
            return (isSameTree(p.left,q.left)) && (isSameTree(p.right,q.right));
        }
        return false;
    }
}

3.2 另一棵树的子树

在这里插入图片描述

思路：

本题基于上一题，然后从根节点先序遍历来逐一判断当前结点是否为相同的树。

  1. 判断root和subRoot是不是就是相同的树 true
  2. root.left或者root.right 中判断是否包含subRoot

判断root中是否包含subRoot => root和subRoot就是相同的树 || root.left中是否包含subRoot || root.right中是否包含subRoot

这三个条件有一个满足，就认为root包含subRoot

代码如下：

public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p==null){
            if (q==null){return true;}
            return false;
        }
        if (q==null){
            if (p==null){return true;}
            return false;
        }
        if (p.val== q.val){
            return (isSameTree(p.left,q.left)) && (isSameTree(p.right,q.right));
        }
        return false;
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        // 边界
        if (root == null && subRoot == null) {
            return true;
        }
        if (root == null || subRoot == null) {
            return false;
        }
        // 恰好root和subRoot就是相同的树 => true
        if (isSameTree(root,subRoot)){
            return true;
        }
        if (isSubtree(root.left,subRoot)){
            return true;
        }
        if (isSubtree(root.right,subRoot)){
            return true;
        }
        return false;
//        return isSameTree(root,subRoot) || isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
    }

3.3 平衡二叉树

在这里插入图片描述

    public int treeTall(TreeNode root){
        if (root==null){
            return 0;
        }
        return 1+Math.max(treeTall(root.left),treeTall(root.right));

    }
    public boolean isBalanced(TreeNode root) {
        if (root==null){
            return true;
        }
        if(Math.abs(treeTall(root.left)-treeTall(root.right))<=1){
            return isBalanced(root.left) && isBalanced(root.right);
        }
        return false;
    }

总结

以上是二叉树的常见操作以及基础面试题，博主之后会更新二叉树的进阶面试题，于💪扣官方给的题解更通俗易懂一点，希望老铁们多多支持，点个关注和赞，感谢！😁😁😁😁

相关文章：

  • 西安专业做网站建设/临沂seo全网营销
  • 如何编辑自己的网站/长春seo外包
  • 制作视频教程/临沂seo
  • 如何简述网站建设流程图/微信营销的特点
  • 深圳坪地疫情最新消息/麒麟seo软件
  • 文山做网站yunling88/怎么做自媒体
  • 北理工操作系统实验合集
  • 【HAL库学习笔记】四、STM32串口与定时器
  • 编程初学者如何缓解迷茫和焦虑？墙裂推荐此文，助你赢在起跑线
  • 图解git原理
  • DOM特效模拟框拖拽
  • ITIL 4 Foundation知识体系-第四章：服务价值体系-2
  • 【备战十四届蓝桥杯 | 开篇】如何高效备战蓝桥杯
  • 北京化工大学2022-2023-1 ACM集训队每周程序设计竞赛（6）题解
  • SpringMVC 5 Rest 风格 5.4 RESTful 案例 5.4.1 需求分析 5.4.2 环境准备
  • Java学习笔记：Java中访问数据库
  • 【程序环境与预处理】
  • 【ASM】字节码操作 转换已有的类 ClassReader 修改字段信息 删除字段 增加字段