面试题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 {}; queue q; q.push(root); while(!q.empty()){ TreeNode* p; int x=q.size(); brant.clear(); for(int i=0;i left!=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 {}; queue q; q.push(root); int y=0; while(!q.empty()){ TreeNode* p; int x=q.size(); brant.clear(); for(int i=0;i left!=NULL) q.push(p->left); if(p->right!=NULL) q.push(p->right); q.pop(); brant.push_back(p->val); } if(y%2==1){ stack brant2; 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(vectorlink){ int x=link.size()/2; for(int i=0;i left==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; queue q; q.push(root->left); q.push(root->right); while(!q.empty()) { TreeNode* p; int y=q.size(); brant.clear(); for(int i=0;i left!=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; } }; 欢迎分享,转载请注明来源:内存溢出
评论列表(0条)