算法进阶之路(七):二叉树面试真题解析及解题技巧总结
2022/1/20 17:16:34
本文主要是介绍算法进阶之路(七):二叉树面试真题解析及解题技巧总结,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
一、二叉树的打印
解题思路:使用递归思路,从根节点依次打印左孩子和右孩子,直至最后一层即可,关键是设计出树的结构,我们先看打印效果:
打印效果相当于一颗平躺的二叉树,顺时针旋转90度,即是一颗我们常见的二叉树,头节点用“H”包裹,左子树用“^”包裹,右子树用“v”包裹。我们固定每个节点的长度len,这里设置的17,然后不足的用空格分别在值的前后均匀补充。
代码如下:
二、打印二叉树的后继节点
解题思路:1.后继节点指的是在二叉树中序遍历中,该节点后面的节点。中序遍历,当前节点是x的最右边节点,则x是当前节点的后继节点。
2.如果有右子树,找到右子树的最左侧节点,即是当前节点的后继节点
如果无右子树,找到父节点,判断当前节点是否是父节点的左孩子,如果是的话,当前节点的父节点即是当前节点的后继节点;如果不是的话,继续向上找,一直到满足条件即可(即当前节点是父节点的左孩子)
代码如下:
三、经典纸张对折
解题思路:自己按照要求对折三次后,发现呈二叉树分布,如图:
使用二叉树的递归套路即可轻易解决。
代码如下:
四、二叉树的递归套路总结
五、递归套路深度实践
题目一
平衡性:左树平衡,右树平衡;左边的子树和右边的子树高度差不超过1
按照如上递归套路,代码如下:
代码如下:
先定义递归的结构体:
递归判断是否平衡树:
题目二:
搜索树:整颗树的节点都不重复,且左边的节点都比右边的节点小;任何一颗子树都是如此。
解题思路:
代码如下:
封装递归的结构体:
递归代码:
这篇关于算法进阶之路(七):二叉树面试真题解析及解题技巧总结的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)