剑指offer学习笔记：8.4 树

面试题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是严格平衡二叉树，红黑树是弱平衡二叉树。