CongYang_96

剑指Offer题解

小知识(2) 读书笔记(1) 题解(6)

/ 注册

全部文章 / 剑指Offer题解（共45篇）

对称的二叉树

1.题目：请实现一个函数，用来判断一棵二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。2.思路：根据上图可知：若满足对称二叉树，必须满足： 1. L->val == R->val 2. L->left->val == R->right-...

2020-11-22

0 485

二叉树中和为某一值的路径

1.题目：输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。1.思路：递归算法三部曲： 1).明白递归函数的功能：FindPath(TreeNode* root,int sum)，从roo...

2020-11-18

0 465

二叉搜索树的后序遍历序列

1. 题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。输入： [4,8,6,12,16,14,10] 返回值： true2.思路此题主要为搜索二叉树的后序遍历，首先搜索二叉树的左子树一定小于...

2020-11-16

0 549

从上往下打印二叉树

1.题目：从上往下打印出二叉树的每个节点，同层节点从左至右打印。{5,4,#,3,#,2,#,1}返回值：[5,4,3,2,1]2.思路：其实就是树的层序遍历，BFS也可称为广度优先遍历利用队列的先入先出特性（FIFO）可以很好的实现从左往右的打印顺序时间复杂度O(n);此题是《把二叉树打印成多行》...

2020-11-15

0 549

孩子们的游戏（约瑟夫环问题）

1.题目：每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中...

2020-11-11

0 821

把二叉树打印成多行

1.题目：从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。输入 {8,6,10,5,7,9,11} 返回值 [[8],[6,10],[5,7,9,11]] 2.思路;其实就是层序遍历：此题最重要的是使用队列，并且记录队列的长度!!!时间复杂度：O(n)题目给的是ArrayList&...

2020-11-11

1 448

二叉树的下一个节点

1.题目：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。2.思路：方法一：暴力解法根据给出的结点求出整棵树的根节点根据根节点递归求出树的中序遍历，存入vector 在vector中查找当前结点，则当前结点的下...

2020-11-10

0 480

二叉搜索树的第K个节点

1.题目：给定一棵二叉搜索树，请找出其中的第k小的结点。输入 {5,3,7,2,4,6,8},3 返回值 {4} 说明按结点数值大小顺序第三小结点的值为4 2.思路：本题最关键的在于是一颗搜索二叉树，那么中序遍历的输出结果就是一个递增的数组！！！！！！ import java.util.Arra...

2020-11-08

0 443

二叉树的镜像

1.题目：操作给定的二叉树，将其变换为源二叉树的镜像。二叉树的镜像定义：源二叉树 8 / \ 6 10 / \ / \ 5 7 9 11 镜像二叉树 ...

2020-11-06

0 462

树的子结构

1.题目：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）2.思路：首先主方法：1.首先需要判断A,B的根节点是否一样。2.如果不一样，判断A的左孩子和B的根节点是否一样，或者判断A的右孩子和B的根节点是否一样。依次找下去，直到找到相同进入次方法如果上述情况...

2020-11-05

0 424