二叉树的层序遍历、前中后序遍历、反转、求深度等操作。一般都要考虑递归方法。

给定一棵二叉搜索树，请找出其中第k大的节点。 二叉搜索树的中序遍历，是满足从小到大的排序性质的，因此要找第k大，直接中序遍历翻转（右根左），找出第k个就行了。 class Solution { public: int k = 0; int res = 0; void dfs(TreeNode* root){ if(root == nullptr |…

序列化二叉树即找一种顺序存储二叉树的节点，并以相同的方式能够读取序列重新构建。 换种说法，就是遍历二叉树，记录每个节点，再以同样的方式遍历就可以还原二叉树。 PS：能基于序列化字符串单独还原树的情况： 层次遍历序列（需标记空节点）。 前序或后序遍历序列（需结合中序，或显式标记空节点，如 [1,2,null,null,3]）。若序列化时未标记空节点，…

层序遍历 vector<vector<int> > Print(TreeNode* pRoot) { // write code here if(pRoot == nullptr) return {}; vector<vector<int>> res; queue<TreeNode*> Q; Q.push(pRoot)…

二叉树的层序遍历，特判版。特判还是比较难的，主要是需要用到tmp.insert(tmp.begin(), x->val);实现从右到左打印 class Solution {public:vector > Print(TreeNode* pRoot) { if (pRoot == nullptr) return {}; vector<ve…

给定一棵二叉树，判断其是否是自身的镜像（即：是否对称） bool dfs(TreeNode* p1, TreeNode* p2){ // 都为nullptr 必对称 if(p1 == nullptr && p2 == nullptr) return true; // 不对称 if(p1 == nullptr || p2 == nul…

简单的思路就是递归中序遍历一遍，存在vector里，然后输出。 通常情况下，中序遍历不可能有O1空间复杂度方法，非递归算法也要用栈来辅助。 三种遍历树的非递归算法总结，可以参考blog：二叉树遍历-非递归算法 - 翁德彪 - 博客园 此处贴一个借助栈的中序遍历非递归算法： void InorderTraverse(BiTree T,Stack *s…

No38：二叉树的深度 简单递归或者层次遍历 class Solution { public: int maxDeep = 0; int curDeep = 0; void dfs(TreeNode* root){ if(root == nullptr) return; curDeep++; maxDeep = max(curDeep, maxDe…