面试题32 - I. 从上到下打印二叉树
描述思路代码 剑指 Offer 32 - II. 从上到下打印二叉树 II
描述思路代码 剑指 Offer 32 - III. 从上到下打印二叉树 III
描述思路代码 剑指 Offer 26. 树的子结构
描述思路代码 剑指 Offer 27. 二叉树的镜像
描述思路代码 剑指 Offer 28. 对称的二叉树
描述思路代码
面试题32 - I. 从上到下打印二叉树 描述思路从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
例如:
输入：
给定二叉树:
[3,9,20,null,null,15,7],
~~~~ ~ 3
~~~~ / ~~~~
~~~~ 9 ~ 20
~~~~ ~~~~~ /
~~~~ ~ 15 ~ 7
输出：[3,9,20,15,7]
~~
条件：节点总数 <= 1000
从头结点开始层次遍历二叉树，用一个队列存储每一个不为null的节点，每一层的子节点存在当前层节点的后面，先进先出，用数组（使用vector动态数组，不用考虑数值个数）存储每个不为null节点的数值。
代码
class Solution {
public:
vector levelOrder(TreeNode* root) {
vector tree;
queue q;
if(root==NULL) return {};
q.push(root);
while(!q.empty()){
TreeNode* p=q.front();//取队列树头节点
if(p->left!=NULL) q.push(p->left);
if(p->right!=NULL) q.push(p->right);//将此节点的左右不为空的子树放到队列里
q.pop();
tree.push_back(p->val);
}
return tree;
}
};
搜索与回溯算法-目录
面试题32 - I. 从上到下打印二叉树
描述思路代码 剑指 Offer 32 - II. 从上到下打印二叉树 II
描述思路代码 剑指 Offer 32 - III. 从上到下打印二叉树 III
描述思路代码 剑指 Offer 26. 树的子结构
描述思路代码 剑指 Offer 27. 二叉树的镜像
描述思路代码 剑指 Offer 28. 对称的二叉树
描述思路代码
剑指 Offer 32 - II. 从上到下打印二叉树 II 描述思路从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
例如:
给定二叉树:
[3,9,20,null,null,15,7],
~~~~ ~ 3
~~~~ / ~~~~
~~~~ 9 ~ 20
~~~~ ~~~~~ /
~~~~ ~ 15 ~ 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
整体思路同上一题，不过在每一层遍历的时候多了一层循环，在上一层遍历结束时，记录当前队列数量（当前层个数），再新建一个单层的数组用来存储当前层的数值，一层循环结束后，将该数组存入需要输出的数组。
代码
class Solution {
public:
vector> levelOrder(TreeNode* root) {
vector> tree;
vector brant;
if(root==NULL)
return {};
queueq;
q.push(root);
while(!q.empty()){
TreeNode* p;
int x=q.size();
brant.clear();
for(int i=0;ileft!=NULL) q.push(p->left);
if(p->right!=NULL) q.push(p->right);
q.pop();
brant.push_back(p->val);
}
tree.push_back(brant);
}
return tree;
}
};
搜索与回溯算法-目录
面试题32 - I. 从上到下打印二叉树
描述思路代码 剑指 Offer 32 - II. 从上到下打印二叉树 II
描述思路代码 剑指 Offer 32 - III. 从上到下打印二叉树 III
描述思路代码 剑指 Offer 26. 树的子结构
描述思路代码 剑指 Offer 27. 二叉树的镜像
描述思路代码 剑指 Offer 28. 对称的二叉树
描述思路代码
剑指 Offer 32 - III. 从上到下打印二叉树 III 描述思路请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
例如:
给定二叉树:
[3,9,20,null,null,15,7],
~~~~ ~ 3
~~~~ / ~~~~
~~~~ 9 ~ 20
~~~~ ~~~~~ /
~~~~ ~ 15 ~ 7
返回其层次遍历结果：
[
[3],
[20,9],
[15,7]
]
整体思路依旧跟上一题一致，唯一的区别在于我用了一个变量记录层数，从0开始记录，当遍历的层数为奇数时，就用一个栈做辅助实现当前层数组的倒序，再将当前层倒序后的数组收入结果数组。
代码
class Solution {
public:
vector> levelOrder(TreeNode* root) {
vector> tree;
vector brant;
if(root==NULL)
return {};
queueq;
q.push(root);
int y=0;
while(!q.empty()){
TreeNode* p;
int x=q.size();
brant.clear();
for(int i=0;ileft!=NULL) q.push(p->left);
if(p->right!=NULL) q.push(p->right);
q.pop();
brant.push_back(p->val);
}
if(y%2==1){
stackbrant2;
for(int i=0;i
搜索与回溯算法-目录
面试题32 - I. 从上到下打印二叉树
描述思路代码
剑指 Offer 32 - II. 从上到下打印二叉树 II
描述思路代码
剑指 Offer 32 - III. 从上到下打印二叉树 III
描述思路代码
剑指 Offer 26. 树的子结构
描述思路代码
剑指 Offer 27. 二叉树的镜像
描述思路代码
剑指 Offer 28. 对称的二叉树
描述思路代码
剑指 Offer 26. 树的子结构
描述
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
例如:
给定的树 A:
~~~~
~
3
~~~~
/
~~~~
~~~~
4
~
5
~~~~
/
~~
1
~
2
给定的树 B：
~~~~
4
~~~~
/
~~
1
~
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
~~
示例 1：
输入：A = [1,2,3], B = [3,1]
输出：false
示例 2：
输入：A = [3,4,5,1,2], B = [4,1]
输出：true
限制：0 <= 节点个数 <= 10000
思路
核心思想是利用两次循环。
第一次是遍历A树的节点，用B树的头结点与其比较，找到符合要求的子树头结点。采用递归的手段，父节点不符合，就看子节点符不符合，只要有一个符合即可。
待找到后，进行第二次循环，这次的循环是比较B的结构是否在A当中，也用递归的手段，若是头结点值相等，就再判断左孩子以及右孩子的结构相不相等（看B树有没有孩子，有则比较，没有就默认这部分相等）。第二个循环也单独写了个函数调用。
代码
class Solution {
public:
//当输入的树的头结点跟大树某个结点值相等，判断子树结构是否相等
bool issame(TreeNode* A,TreeNode* B)
{
if(B==NULL) return true;//子树遍历结束，前面元素都相等
if(A==NULL) return false;//大树遍历结束，子树还没结束，子树超数
if(A->val!=B->val)//有元素不相等，则不是
return false;
return issame(A->left,B->left)&&issame(A->right,B->right);
}
bool isSubStructure(TreeNode* A, TreeNode* B) //判断子树是否存在
{
if(A==NULL||B==NULL)//都是空树不存在
return false;
else if(A->val==B->val&&issame(A,B))//当头结点相等且子树结构相等
return true;
//头结点不相等时，去找大树的子节点
return isSubStructure(A->left,B)||isSubStructure(A->right,B);
}
};
搜索与回溯算法-目录
面试题32 - I. 从上到下打印二叉树
描述思路代码
剑指 Offer 32 - II. 从上到下打印二叉树 II
描述思路代码
剑指 Offer 32 - III. 从上到下打印二叉树 III
描述思路代码
剑指 Offer 26. 树的子结构
描述思路代码
剑指 Offer 27. 二叉树的镜像
描述思路代码
剑指 Offer 28. 对称的二叉树
描述思路代码
剑指 Offer 27. 二叉树的镜像
描述
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
例如输入：
~~~~
~
4
~~~~
/
~~~~
~~~
2
~~~
7
~~
/
~~~
/
~
1 3
~
6 9
镜像输出：
~~~~
~
4
~~~~
/
~~~~
~~~
7
~~~
2
~~
/
~~~
/
~
9 6
~
3 1
**示例 **：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
限制：0 <= 节点个数 <= 1000
思路
利用递归函数，直接修改二叉树，调换每个节点的左右节点，同时调换的还是镜像过的左右节点。
代码
class Solution {
public:
TreeNode* mirrorTree(TreeNode* root) {
if(root==NULL)
return root;
TreeNode* p=root->left;
root->left=mirrorTree(root->right);
root->right=mirrorTree(p);
return root;
}
};
搜索与回溯算法-目录
面试题32 - I. 从上到下打印二叉树
描述思路代码
剑指 Offer 32 - II. 从上到下打印二叉树 II
描述思路代码
剑指 Offer 32 - III. 从上到下打印二叉树 III
描述思路代码
剑指 Offer 26. 树的子结构
描述思路代码
剑指 Offer 27. 二叉树的镜像
描述思路代码
剑指 Offer 28. 对称的二叉树
描述思路代码
剑指 Offer 28. 对称的二叉树
描述
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
~~~~
~
1
~~~~
/
~~~~
~~~
2
~~~
2
~~
/
~~~
/
~
3 4
~
4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
~~~~
~
1
~~~~
/
~~~~
~~~
2
~~~
2
~~~~
~~~~
~~~~
3
~~~~
3
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false
限制：0 <= 节点个数 <= 1000
思路
首先分析一下对称树的样子。
空树或者只有一层的话，一定是对称树；
从二层往下，每层必须满足左右对称，如果把null的位置填充为一个默认值（我用的-99），然后参考打印二叉树的做法，把每一层存到一个数组里，数组大小一定是偶数，再设置一个判断该数组元素是否左右对称的函数，每遍历一层就判断一次，一旦不对称，则不是对称二叉树，若每一层都左右对称，则该树是对称二叉树。
代码
class Solution {
public:
bool isdui(vector link){
int x=link.size()/2;
for(int i=0;ileft==NULL&&root->right==NULL) return true;//只有头结点
if(root->left==NULL||root->right==NULL) return false;//有一边没有
if(root->left->val!=root->right->val) return false;//第二层两个不一样一定不对称
//从第三行开始，一行一行看是否对称，有缺失就补全，我用的-99
vector brant;
queueq;
q.push(root->left);
q.push(root->right);
while(!q.empty())
{
TreeNode* p;
int y=q.size();
brant.clear();
for(int i=0;ileft!=NULL){
q.push(p->left);
brant.push_back(p->left->val);
}
else
brant.push_back(-99);
if(p->right!=NULL){
q.push(p->right);
brant.push_back(p->right->val);
}
else
brant.push_back(-99);
q.pop();
}
if(!isdui(brant)) return false;
}
return true;
}
};
