【数据结构】 二叉树面试题讲解->叁

本文涉及的产品
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
云解析 DNS,旗舰版 1个月
全局流量管理 GTM,标准版 1个月
简介: 【数据结构】 二叉树面试题讲解->叁

🌏引言

二叉树的操作算法是笔试面试中较为常见的题目。

本文将着重介绍平时面试中常见的关于二叉树的应用题目,马上要进行秋招了。希望对你们有帮助 _😀

🌲根据二叉树创建字符串

🐱‍👤题目描述:

给你二叉树的根节点 root ,请你采用前序遍历的方式,将二叉树转化为一个由括号和整数组成的字符串,返回构造出的字符串。

空节点使用一对空括号对 “()” 表示,转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

/**
 * 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 String tree2str(TreeNode root) {
    }
}

🐱‍🐉示例:

📌示例一

📌示例二

🐱‍👓思路解析

我们可以使用递归的方法得到二叉树的前序遍历,并在递归时加上额外的括号。

会有以下 4种情况:

  • 如果当前节点有两个孩子,那我们在递归时,需要在两个孩子的结果外都加上一层括号;
  • 如果当前节点没有孩子,那我们不需要在节点后面加上任何括号;

  • 如果当前节点只有左孩子,那我们在递归时,只需要在左孩子的结果外加上一层括号,而不需要给右孩子加上任何括号;

  • 如果当前节点只有右孩子,那我们在递归时,需要先加上一层空的括号 ‘()’\text{`()'}‘()’ 表示左孩子为空,再对右孩子进行递归,并在结果外加上一层括号。

那我们具体应该怎么做呢?

做法如下:

  • 由于我们需要返回一个字符串,我们这里创建一个StringBuilder类的对象stringbuilder来存放我们的字符串
  • 接下来我们创建一个方法tree2strChild用于遍历二叉树,并将二叉树变为字符串
  • 在tree2strChild方法里,我们首先将根节点放入到字符串stringbuilder中
  • 然后对左子树进行判断,若不为null
  • 则字符串添加一个左括号
  • 然后递归左子树
  • 递归完后添加右括号
  • 若为null,且右边不为null
  • 则字符串添加()
  • 接下来判断右子树
  • 若右子树为null
  • 直接返回就好
  • 若不为null
  • 字符串添加左括号
  • 然后递归右树
  • 追后字符串添加右括号即可

🐱‍🏍代码完整实现:

/**
 * 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 String tree2str(TreeNode root) {
        if(root == null) {
            return null;
        }
        StringBuilder stringBuilder = new StringBuilder();
        tree2strChild(root,stringBuilder);
        return stringBuilder.toString();
    }
    public void tree2strChild(TreeNode t,StringBuilder stringBuilder) {
        if(t == null) {
            return;
        }
        stringBuilder.append(t.val);
        if(t.left != null) {
            stringBuilder.append("(");
            tree2strChild(t.left,stringBuilder);
            stringBuilder.append(")");
        }else {
            //左边为空了
            if(t.right != null) {
                //右边不为空
                stringBuilder.append("()");
            }else {
                //右边为空
                return ;
            }
        }
        if(t.right == null) {
            return;
        }else {
            stringBuilder.append("(");
            tree2strChild(t.right,stringBuilder);
            stringBuilder.append(")");
        }
    }
}

🌴判断一棵树是不是完全二叉树

🐱‍👤题目描述:

给你一棵树让你判断是不是完全二叉树

🐱‍🐉示例:

🐱‍👓思路解析:

其实这道题与博主前面所讲的层序遍历类似

  • 我们依旧定义一个队列,先将根结点入队
  • 如果队列不为空我们就进入循环
  • 将队列的元素进行出栈并赋给cur变量
  • 如果cur不等于null,我们就将cur的左树和右树进行入队
  • 不用管左树右树是否为null;
  • 如果cur为null则跳出循环

这时候队列元素为

这时候我可以将队列进行出队,元素全部为null,则为完全二叉树

🐱‍🏍完整代码实现:

boolean isCompleteTree(TreeNode root){
        if(root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if(cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;
            }
        }
        while (!queue.isEmpty()) {
            TreeNode tmp = queue.poll();
            if(tmp != null) {
                return false;
            }
        }
        return true;
    }

🎋二叉树的前序遍历(迭代实现)

🐱‍👤题目描述:

给你二叉树的根节点 root ,返回它节点值的 前序 遍历。

/**
 * 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 List<Integer> preorderTraversal(TreeNode root) {
    }
}

🐱‍🐉示例:

🐱‍👓思路解析:

我们创建一个栈来实现迭代的前序遍历

  • 我们用变量cur来进行遍历
  • 首先我们对cur进行判断,若不为null,
  • 则将cur入栈,并将该元素存储在顺序表list里
  • 然后遍历cur的左子树

将上述操作放入一个循环里,循环条件就为cur是否为null;

当cur为null时,我们就将栈中元素进行出栈赋给变量top

并用cur访问top的右子树

上面的操作我们再放入一个外循环里,条件为cur不为null或者栈不为空

🐱‍🏍代码实现如下:

/**
 * 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 List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) {
            return list;
        }
        TreeNode cur = root;
        Deque<TreeNode> stack = new ArrayDeque<>();
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                list.add(cur.val);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
        return list;
    }
}

🍀二叉树的中序遍历(迭代实现)

🐱‍👤题目描述:

给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。

/**
 * 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 List<Integer> inorderTraversal(TreeNode root) {
    }
}

🐱‍🐉示例:

🐱‍👓思路解析:

与前序遍历步骤大致相同

不同的是中序遍历需要先在顺序表内存储左节点

也就是说我们需要先将该节点的左节点全部入栈后,然后再出栈到顺序表内

接下来访问右子树

🐱‍🏍代码实现:

/**
 * 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 List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) {
            return list;
        }
        TreeNode cur = root;
        Deque<TreeNode> stack = new ArrayDeque<>();
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            list.add(top.val);
            cur = top.right;
        }
        return list;
    }
}

🎄二叉树的后续遍历(迭代实现)

🐱‍👤题目描述:

给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历 。

/**
 * 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 List<Integer> postorderTraversal(TreeNode root) {
    }
}

🐱‍🐉示例:

🐱‍👓思路解析:

入栈思路与前序遍历和中序遍历思路相同

只是出栈不同

  • 我们首先需要得到栈顶元素,但不出栈,依旧用top表示
  • 如果top右节点为null,则说明top为叶子结点,可以出栈进入到顺序表类
  • 如果不为null,则遍历top的右节点

当然现在的思路还有一个问题,我们可能重复遍历top的右子树,最终程序崩溃

所以我们这里加一个变量pero进行判断,若相等则不再遍历该右节点

🐱‍🏍代码完整实现:

/**
 * 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 List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) {
            return list;
        }
        TreeNode cur = root;
        TreeNode prev = null;
        Deque<TreeNode> stack = new ArrayDeque<>();
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if(top.right == null || top.right == prev) {
                list.add(top.val);
                stack.pop();
                prev = top;
            }else {
                cur = top.right;
            }
        }
        return list;
    }
}

⭕总结

关于《【数据结构】 二叉树面试题讲解->叁》就讲解到这儿,感谢大家的支持,欢迎各位留言交流以及批评指正,如果文章对您有帮助或者觉得作者写的还不错可以点一下关注,点赞,收藏支持一下!

相关文章
|
4天前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
31 8
|
27天前
|
算法 前端开发 Java
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
这篇文章总结了单链表的常见面试题,并提供了详细的问题分析、思路分析以及Java代码实现,包括求单链表中有效节点的个数、查找单链表中的倒数第k个节点、单链表的反转以及从尾到头打印单链表等题目。
29 1
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
|
27天前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
16 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
27天前
|
存储 算法 搜索推荐
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
17 0
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
|
29天前
|
Java
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
25 1
|
29天前
|
算法 Java C语言
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)
22 1
|
9天前
|
存储 NoSQL Redis
Redis常见面试题:ZSet底层数据结构,SDS、压缩列表ZipList、跳表SkipList
String类型底层数据结构,List类型全面解析,ZSet底层数据结构;简单动态字符串SDS、压缩列表ZipList、哈希表、跳表SkipList、整数数组IntSet
|
1月前
|
存储
【数据结构】二叉树链式结构——感受递归的暴力美学
【数据结构】二叉树链式结构——感受递归的暴力美学
|
11天前
|
算法 Java
JAVA 二叉树面试题
JAVA 二叉树面试题
12 0
|
27天前
|
存储 算法
探索数据结构:分支的世界之二叉树与堆
探索数据结构:分支的世界之二叉树与堆