面试题58：二叉树的下一个节点
给定一个二叉树和其中一个节点，如何找到中序遍历顺序的下一个节点？树中的节点除了有两个分别指向左右子节点的指针外，还有一个指向父节点的指针。
牛客网链接https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e?tpId=13&&tqId=11210&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking/* struct TreeLinkNode { int val; struct TreeLinkNode *left; struct TreeLinkNode *right; struct TreeLinkNode *next; TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) { } }; */ class Solution { public: TreeLinkNode* GetNext(TreeLinkNode* pNode) { if (pNode == NULL) { return NULL; } // 第一种情况当前节点有右子节点，找到右子树最左节点 TreeLinkNode* result = NULL; if (pNode->right != NULL) { TreeLinkNode* cur = pNode->right; while(cur->left != NULL) { cur = cur->left; } result = cur; } else if (pNode->next != NULL) { if (pNode->next->left == pNode) { // 第二种情况，当前节点没有右子树，但是是其根节点的左子节点。则根节点即为要找节点 result = pNode->next; } else { // 第三种情况，也是最复杂的一种情况 // 当前节点没有右子节点，且为其父节点的右子节点 // 沿着父节点向上遍历，直到找到某节点，该节点为其父节点的左子节点，则该节点父节点即为所求 while(pNode != NULL && pNode->next != NULL && pNode->next->left != pNode) { pNode = pNode->next; } if (pNode != NULL) { result = pNode->next; } } } return result; } };
解题思路：
中序遍历的遍历顺序是左根右，根据遍历顺序进行分析。中序遍历用栈实现的过程是遍历左子树，并将当前节点入栈，当节点不再有左子树，栈顶出，同时入栈顶元素右子树节点，再重复不断遍历右子树节点的左子树，直到没有左子节点再次出栈的过程。如图二叉树，其中序遍历结果为d,b,h,e,i,a,f,c,g
二叉树没画指向父节点指针
如果当前节点有右子树，则其中序遍历的下一个节点为右子树的最左的节点。譬如a的下一个节点是f。
如果当前节点没有右子树，但是有父节点且当前节点为根节点的左子树，则当前节点的下一个节点为其父节点。譬如g的下一个节点是c。
如果当前节点没有右子树，且其为其父节点的右子树节点，譬如节点i，需要沿着父节点向上遍历，直到找到一个节点，该节点为其父节点的左子节点，则其父节点就是我们要找的节点。此图中，b是a的子节点，则a就是我们要找的节点。
如果当前节点没有右子树且当前节点没有父节点，即当前节点为只有左子树的根节点，则根节点为中序遍历终止，没有下一遍历节点。
寻找过程
面试题59：对称二叉树
请实现一个函数，用来判断一棵树是不是对称的
leetcode链接 https://leetcode-cn.com/problems/symmetric-tree//** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isSymmetric(TreeNode* root1, TreeNode* root2) { if (root1 == NULL && root2 == NULL) { return true; } if (root1 == NULL || root2 == NULL) { return false; } if (root1->val != root2->val) { return false; } return isSymmetric(root1->left, root2->right) && isSymmetric(root1->right, root2->left); } bool isSymmetric(TreeNode* root) { if (root == NULL) { return true; } return isSymmetric(root->left, root->right); } };
解题思路：递归。左子树的左子树和右子树的右子树，左子树的右子树和右子树的左子树需要相同。
面试题60：把二叉树打印成多行
从上到下按层打印二叉树，同一层的节点按照从左到右打印，每一层打印到下一层。
牛客网链接 https://www.nowcoder.com/practice/445c44d982d04483b04a54f298796288?tpId=13&&tqId=11213&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class Solution { public: vector<vector<int> > Print(TreeNode* pRoot) { queue<TreeNode*> tree; vector<vector<int>> result; if (pRoot == NULL) { return result; } tree.push(pRoot); while(!tree.empty()) { int len = tree.size(); vector<int> level; for(int i = 0; i < len; i++) { TreeNode* tmp = tree.front(); level.push_back(tmp->val); if (tmp->left) { tree.push(tmp->left); } if (tmp->right) { tree.push(tmp->right); } tree.pop(); } result.push_back(level); } return result; } };
解题思路：广度优先遍历，用队列
面试题61：按之字形顺序打印二叉树
按之字形顺序打印二叉树，即第一行那从左到右打印，第二行按从右到左打印，第三行从左到右打印，其余行依次类推。
牛客网链接 https://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0?tpId=13&&tqId=11212&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class Solution { public: vector<vector<int> > Print(TreeNode* pRoot) { vector<vector<int>> result; if (pRoot == NULL) { return result; } stack<TreeNode*> level1, level2; level1.push(pRoot); while(!level1.empty() || !level2.empty()) { vector<int> level; while (!level1.empty()) { TreeNode* tmp = level1.top(); level1.pop(); level.push_back(tmp->val); if (tmp->left) { level2.push(tmp->left); } if (tmp->right) { level2.push(tmp->right); } } if (level.size() > 0) { result.push_back(level); continue; } while (!level2.empty()) { TreeNode* tmp = level2.top(); level2.pop(); level.push_back(tmp->val); if (tmp->right) { level1.push(tmp->right); // 注意这一行要先入右节点 } if (tmp->left) { level1.push(tmp->left); } } result.push_back(level); } return result; } };
解题思路：因为是之字形，下一行遍历顺序和上一行遍历顺序相反，因此需要用先进后出的栈结构。因为栈结构是先进后出，而层序遍历需要每行遍历完全才能遍历下一行，因此当前行和下一行不能用一个栈。设计两个栈结构，分别用于存当前遍历行元素，和当前遍历元素的左右子树，即下一即将遍历行元素。
面试题62：序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树
leetcode链接 https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof/
解题思路：
剑指offer上的思路是将树序列化成前序遍历，与前序遍历的区别是空节点不直接跳过，而是使用特殊字符进行替代。
反序列化时因为前序遍历是根左右，譬如序列化得到的是"1,2,4,$,$,$,3,5,$,$,6,$,$"，分析1即为根节点，2为当前根节点左子节点，4为2的左子节点，遇到空字符，说明4的左子节点为空，接下来还是空字符，代表4的右子节点也为空，接下来重建2的右子节点，还是空，接下来重建1的右子节点，为3，依次向后重建。
我感觉用层次遍历进行序列化和重建更加直观和简单，既然没有要求，可以用层次遍历来重建。
面试题63：二叉搜索树的第k个节点
给定一个二叉搜索树，求其中第k大节点
leetcode链接 https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof//** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: void orderTree(TreeNode* root, vector<int>& tree, int k) { if (root == NULL || tree.size() >= k) { return; } if (root->right) { orderTree(root->right, tree, k); } tree.push_back(root->val); if (root->left) { orderTree(root->left, tree, k); } return; } int kthLargest(TreeNode* root, int k) { vector<int> tree; orderTree(root, tree, k); /* for(int i = 0; i < tree.size(); i++) { cout << tree[i] << endl; } */ if (tree.size() < k) { return tree[0]; } return tree[k - 1]; } };
解题思路：
中序遍历二叉搜索树得到的是有序递增序列，很容易得到第k大节点。
升级了下，因为是第k大，因此递减数组比较容易操作，将中序遍历左右根改为右左根。当遍历数组tree长度大于k的时候，说明第k大元素已经遍历过了，可以终止遍历。
面试题64：数据流中的中位数
如果从数据流中读出奇数个数值，那么中位数就是所有数值排序后，位于中间的那个数值。如果是偶数个数，那么中位数就是中间两个数的平均值
leetcode链接 https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/
解题思路：
考虑使用什么容器来存储数据流。当有新的数据从数据流中读出来，这些数据就插入到这个容器中，那这个数据结构选用什么比较合适呢？
思路1：数组
数组是简单的数据容器，如果数组没有排序，用快排中partition函数来找出数组中的中位数，在没有排序的数组中插入和找到中位数的时间复杂度分别为o(1)和o(n)
我们还可以在往数组里插入新元素的时候使数组保持有序。这时由于可能移动o(n)个元素，因此需要o(n)时间完成插入。找到中位数的时间复杂度为o(1)
可以用链表或有序链表代替数组，时间复杂度同数组。
思路2：二叉搜索树可以把插入新元素的平均时间降低到o(logn)。但是当二叉搜索树极度不平衡，将退化成有序链表。为了避免二叉搜索树的最差情况，可以利用平衡二叉树，即avl树，但是大部分编程语言库中没有实现这个数据结构，因此分析其余方法。试试用set的红黑树来进行操作
思路3:使用大顶堆和小顶堆。将元素以中位数为分隔，小于中位数在左面，大于中位数在右边。左面用大顶堆来表示，右边用小顶堆来表示。往堆中插入元素的时间复杂度是log(n)，获取中位数的时间是o(1)。
接下来考虑一些细节：首先要保证数据均匀分配到两个堆中，因此两个堆中数据的数目差不超过1。为了实现平均分配，可以在数据总数目是偶数的时候把新数据插入小顶堆中，否则插入大顶堆中。
还要保证小顶堆中元素都大于大顶堆中元素，当数据总数是偶数，按照前面规则，新数据将插入小顶堆中，但是当前数据要比大顶堆中一些数据要小时，该怎么办呢
可以把新数据先插入大顶堆中，然后把大顶堆中最大数据插到小顶堆中。同理当当前数据需要插入小顶堆但是较小的情况。
| 数据结构 | 插入的时间效率 | 得到中位数的时间效率 |
|---|---|---|
| 没有排序的数组 | 1 | n |
| 排序的数组 | n | 1 |
| 排序的链表 | n | 1 |
| 二叉搜索树 | 平均logn，最差n | 平均logn，最差n |
| avl树 | logn | 1 |
| 最大堆和最小堆 | logn | 1 |
【c++拾遗】avl树和红黑树（RB）区别
参考链接：https://blog.csdn.net/Gosick_Geass_Gate/article/details/88556840简单来说，都是平衡二叉搜索树，只是对平衡的要求不同，维持平衡的方式不同。avl是严格平衡二叉树，红黑树是弱平衡二叉树。
网友评论