- 从上向下打印二叉树的每个节点， 同一层的节点按照从左到右的顺序打印。
- 判断一棵树是否是完全二叉树。
- 将一棵完全二叉树层次遍历转化为一个链表。（不用队列）
1、思路：
可以使用双端队列deque容器，头负责打印，尾负责接受子节点，直到deque中没有元素为止。
1 void PrintBiTreeBreadth(BiTreeNode* root) 2 { 3 if (root == NULL) return; 4 deque dequeBiTreeNode; 5 dequeBiTreeNode.push_back(root); 6 while (dequeBiTreeNode.size()) 7 { 8 BiTreeNode* node = dequeBiTreeNode.front(); 9 dequeBiTreeNode.pop_front();10 printf("%d\t", node->nValue);11 12 if (node->pLeft)13 dequeBiTreeNode.push_back(node->pLeft);14 if (node->pRight)15 dequeBiTreeNode.push_back(node->pRight);16 }17 printf("\n");18 }
2、思路：
面试hulu的时候一道热身题，完全二叉树是一棵最后一层从左到右分布，其他层节点均满，最后一层可能不满的二叉树。我当时的思路是只要遇到一个没有孩子或是只有左孩子的节点，接下去层次遍历的节点必须是叶子节点。如果遇到只有右孩子没有左孩子的节点，直接可以判断不是完全二叉树。后来，发现一个更好的算法，借助哨兵节点NULL，当层次遍历进入NULL时，后序进入的必须是NULL，否则说明还有节点存在，则不符合完全二叉树的性质。
1 bool IsComplete(BinaryTreeNode* root) 2 { 3 if (root == NULL) return false; 4 5 deque dq; 6 BinaryTreeNode* node; 7 dq.push_back(root); 8 bool flag = false; 9 10 while (!dq.empty())11 {12 node = dq.front();13 dq.pop_front();14 if (node)15 {16 if (flag)17 return false;18 dq.push_back(node->m_pLeft);19 dq.push_back(node->m_pRight);20 }21 else22 flag = true;23 }24 return true;25 }
3、思路：
面试微软的时候，一道层次遍历二叉树转化为双向链表的题。当时以为题目出错了，应该是二叉查找树转为为有序双向链表。结果面试官提示，节点可以有4个指针，另外两个分别是prev和next，用于双向链表的指针。但是最后也没有搞定，只写了一层转化为双向链表，层与层之间怎么着都链接不起来。后来在网上查到了这样一道题，感觉和我遇到的面试题很像，赶紧摘录下来。
1 typedef struct _TreeNode 2 { 3 int value; 4 struct _TreeNode* next; 5 struct _TreeNode* left; 6 struct _TreeNode* right; 7 }TreeNode; 8 9 TreeNode* Tree2ListByLevel(TreeNode* root)10 {11 if (root == NULL) return NULL;12 TreeNode *pre = root, *cur = root;13 14 pre->next = cur->left;15 if (cur->left != NULL)16 cur->left->next = cur->right;17 else18 return root;19 if (cur->right == NULL)20 return root;21 cur = cur->next;22 23 while (cur != NULL)24 {25 if (cur->left != NULL)26 cur->left->next = cur->right;27 if (pre->right != NULL)28 pre->right->next = cur->left;29 cur = cur->next;30 pre = pre->next;31 }32 return root;33 }