牛客786963925号

题解

/ 注册

全部文章 / 题解（共8篇）

题解 | #序列化二叉树#

解法一：前序遍历题目要求：1. 访问二叉树，并将访问结果存到一个字符串中返回，即：「二叉树的序列化」；2. 访问得到的字符串，重构出二叉树，即：「二叉树的反序列化」。显而易见的是，在二叉树的序列化过程中，需要「遍历二叉树」，因此可采用二叉树的遍历方法之一：「前序遍历」来实现。这是因为：前序遍历是...

C++ 二叉树先序遍历层次遍历队列递归

2021-08-08

0 555

题解 | #实现二叉树先序，中序和后序遍历#

解法一：递归「二叉树的先序遍历」的思路是：先访问根结点，再访问左子树，最后访问右子树；「二叉树的中序遍历」的思路是：先访问左子树，再访问根结点，最后访问右子树；「二叉树的后序遍历」的思路是：先访问左子树，再访问右子树，最后访问根结点；下图以「先序遍历」为例进行展示：基于上述思路，可以得...

C++ 二叉树中序遍历先序遍历后序遍历递归栈

2021-07-14

20 2109

题解 | #平衡二叉树#

解法一：自顶向下一棵二叉树为「平衡二叉树」的条件为：该树为空树，或者其左右子树的高度差最大为1。因此，判断一棵二叉树是否平衡需要求其子树高度，并比较左右子树高度差。因此此题的解题步骤如下：设计「求二叉树高度」的函数getHeight(root)，作用是求以root为根结点的二叉树高度；遍历...

二叉树 C++ 递归平衡二叉树

2021-07-12

8 1185

题解 | #判断一棵二叉树是否为搜索二叉树和完全二叉树#

解法一：中序遍历（递归）+ 层次遍历一棵「二叉搜索树」需要满足要求：对于每个结点，左子树上的所有结点小于它，右子树上的所有结点大于它。判断一棵二叉树是否为「二叉搜索树」的通用方法为：对该二叉树进行中序遍历，若遍历结果为「严格」单调递增的，则是一棵二叉搜索树，否则不是。这是因为：中序遍历的步骤是...

C++ 二叉树中序遍历队列递归栈层次遍历二叉搜索树完全二叉树

2021-07-12

2 1114

题解 | #把二叉树打印成多行#

解法一：递归递归方法通过定义递归函数helper，遍历树的每一层，并将结果放入结果数组res的相应位置，因此需要定义level变量以记录当前访问到的层数。在完成对某一凑层的遍历时，按照相同方式递归地访问左孩子和右孩子，且层数加1。实现代码如下： /* struct TreeNode { ...

C++ 二叉树队列递归层次遍历

2021-07-08

4 700

题解 | #按之字形顺序打印二叉树#

解法一：使用队列据题意，需要按照每一层的方式打印二叉树，因此较为直接的解法为「层次遍历」。二叉树的层次遍历通过队列实现较为方便，步骤如下：初始情况，根结点入队列；定义变量size记录当前队列长度；对于「当前队列」，遍历其所有元素：依次出队列、访问该元素、左右孩子入队列。注意：新入队列的「...

C++ 二叉树队列栈

2021-07-08

29 2436

题解 | #对称的二叉树#

解法一：递归方法据题意，对称二叉树定义为：「若一棵二叉树与其镜像二叉树是相同的，则其是对称的二叉树」。因此，判断一棵二叉树是否是对称的，需要从根结点开始，不断地比较左右子树的对称情况，过程如图所示。从根结点（结点）0开始，判断其左右子树是否对称，即判断「结点1所在子树」和「结点2所在子树」是否...

C++ 二叉树队列递归

2021-07-08

3 912

题解 | #二叉树的下一个结点#

解法一：暴力解法据题意，「某结点的下一个结点」定义为「中序遍历」后的下一个结点。因此暴力解法的步骤为：根据输入的结点以及next指针，先求得二叉树的根结点root；利用root进行二叉树的中序遍历，并定义数组储存中序遍历的结果；遍历该数组，得到「下一个结点」。注意：二叉树的中序遍历步骤...

C++ 二叉树中序遍历

2021-07-07

8 898