AI 助理
备案控制台
开发者社区 云计算 文章 正文

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

2022-10-20 95
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 二叉树的操作及常见面试题

前言

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

二叉树的概念及性质

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

一、四种遍历方式

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

前、中、后序遍历为深度优先遍历（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;
    }

总结

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

关键词：
二叉树面试
ngu6wsufvctzi
目录
相关文章
快乐的流畅
|
6月前
|
C++
二叉树进阶面试题（精华总结）【C++版本】
二叉树进阶面试题（精华总结）【C++版本】
快乐的流畅
53 1
Mylvzi
|
6月前
数据结构之二叉树及面试题讲解（二）
数据结构之二叉树及面试题讲解
Mylvzi
51 0
Hdnw
|
6月前
力扣面试经典题之二叉树
力扣面试经典题之二叉树
Hdnw
45 0
遇事问春风乄
|
存储 算法
【数据结构】 二叉树面试题讲解-＞叁
【数据结构】 二叉树面试题讲解-＞叁
遇事问春风乄
59 1
遇事问春风乄
|
存储
【数据结构】 二叉树面试题讲解-＞壹I（二）
【数据结构】 二叉树面试题讲解-＞壹I（二）
遇事问春风乄
79 0
2的n次方_
|
2月前
|
算法
二叉树面试题
本文介绍了二叉树相关的几个经典算法问题。首先讲解了如何判断两棵树是否完全相同（LeetCode 100），并给出了代码示例。接着讨论了如何判断一棵树是否是另一棵树的子树（LeetCode 572），详细分析了子树的定义及判断方法。然后介绍了翻转二叉树（LeetCode 226）的实现方法，即在遍历时交换每个节点的左右子树。随后探讨了如何判断一棵树是否是对称的（LeetCode 101），通过对左右子树的递归比较来实现。最后分析了平衡二叉树的概念（LeetCode 110）及判断方法，并给出了优化后的代码示例。此外，还简要介绍了二叉树遍历及二叉树最近公共祖先（LeetCode 236）的问题
2的n次方_
28 6
二叉树面试题
刘大猫.
|
25天前
|
算法 Java
JAVA 二叉树面试题
JAVA 二叉树面试题
刘大猫.
15 0
炫酷的伊莉娜
|
6月前
【一刷《剑指Offer》】面试题 23：从上往下打印二叉树
【一刷《剑指Offer》】面试题 23：从上往下打印二叉树
炫酷的伊莉娜
57 0
炫酷的伊莉娜
|
6月前
【一刷《剑指Offer》】面试题 19：二叉树的镜像
【一刷《剑指Offer》】面试题 19：二叉树的镜像
炫酷的伊莉娜
45 0
炫酷的伊莉娜
|
6月前
【一刷《剑指Offer》】面试题 6：重建二叉树
【一刷《剑指Offer》】面试题 6：重建二叉树
炫酷的伊莉娜
34 0

热门文章

最新文章

  • 1
    面试必问的4种单点登录的实现方式，你知道几个？
  • 2
    flink面试问题总结（3）
  • 3
    经典软件面试题（2）
  • 4
    C# 面试题解析-请遍历页面上所有的TextBox控件并给它赋值为string.Empty
  • 5
    面试题1：赋值运算符函数
  • 6
    超有用的sql查询语句。项目、面试都有用
  • 7
    大厂高频面试真题详解：最长无重复字符的子串
  • 8
    webRTC（十五），2024最新Android中级面试题目汇总解答
  • 9
    vue基础面试题(day01)
  • 10
    【每日算法Day 74】经典面试题：约瑟夫环，我敢打赌你一定不会最后一种方法！
  • 1
    Android面试题之View的invalidate方法和postInvalidate方法有什么区别
    59
  • 2
    面试一口气说出Spring的声明式事务@Transactional注解的6种失效场景
    120
  • 3
    Android面试题之自定义View注意事项
    58
  • 4
    Android面试题之kotlin中怎么限制一个函数参数的取值范围和取值类型等
    79
  • 5
    Android面试题之 Kotlin中退出迭代器的方式有哪些
    40
  • 6
    Java面试题：描述Java垃圾回收的基本原理，以及如何通过代码优化来协助垃圾回收器的工作
    89
  • 7
    Java面试题：请解释Java中的永久代（PermGen）和元空间（Metaspace）的区别
    222
  • 8
    Java面试题：方法区在JVM中存储什么内容？它与堆内存有何不同？
    71
  • 9
    Java面试题：JVM的内存结构有哪些主要部分？请简述每个部分的作用
    60
  • 10
    Java面试题：请解释Java内存模型(JMM)是什么，它如何保证线程安全？
    110

    • 相关课程

    更多
  • Java面试疑难点解析 - 面试技巧及语言基础
  • Java面试疑难点解析 - Java Web开发
  • Java面试疑难点解析 - 系统架构及项目设计

    • 相关电子书

    更多
  • 阿里云技术面试红宝书
  • 超全算法笔试-模拟题精解合集
  • 程序员面试宝典
    • 下一篇
    手把手教你白嫖阿里云服务器(免费领服务器)