DS

对于成长，年龄不是记号，责任才是标志，长大就是一种勇气和担当。 成长是生命的延续、责任的延续！–林海音

二叉树的面试题(C版本)

//1.二叉树的前序遍历. typedef struct TreeNode Node; //Res指用来保存树里面每一个结点的内存空间 //index向空间哪一个位置保存 void _PreOrder(Node* pRoot, int* pRes, int* index){ if (pRoot){ //遍历根节点 pRes[*index] = pRoot->val; (*index)++; //遍历根的左子树 _PreOrder(pRoot->left, pRes, index); //遍历根的右子树 _PreOrder(pRoot->right, pRes, index); } } //获取二叉树结点个数 int GetTreeSize(Node* pRoot){ if (NULL == pRoot){ return 0; } return GetTreeSize(pRoot->left) + GetTreeSize(pRoot->right) + 1; } //将二叉树中每个结点值域保存到一段连续空间中返回 int* preorderTraversal(struct TreeNode* root, int* returnSize){ *returnSize = GetTreeSize(root); int* pRes = (int*)malloc(sizeof(int)*(*returnSize)); //开辟空间 if (NULL == pRes){ assert(0); return NULL; } int index = 0; _PreOrder(root,pRes,returnSize); return pRes; } //2.二叉树的中序遍历. typedef struct TreeNode Node; void _InOrder(Node* root, int* pRes, int* index){ if (root){ //遍历根的左子树 _InOrder(root->left, pRes, index); //遍历根节点 pRes[*index] = root->val; (*index)++; //遍历根的右子树 _InOrder(root->right, pRes, index); } } int GetTreeSize(Node* root){ if (NULL == root){ return 0; } return GetTreeSize(root->left) + GetTreeSize(root->right) + 1; } //将二叉树中每个结点值域保存到一段连续空间中返回 int* inOrderTraversal(struct Node* root, int* returnSize){ *returnSize = GetTreeSize(root); int* pRes = (int*)malloc(sizeof(int*)(*returnSize)); if (NULL == pRes){ assret(0); return NULL; } int index = 0; _Inorder(root, pRes, &index); return pRes; } //3.二叉树的后序遍历. typedef struct TreeNode Node; void _PosOrder(Node* pRoot, int* pRes, int* index){ if (pRoot){ //遍历根的左子树 _PosOrder(pRoot->left, pRes, index); //遍历根的右子树 _PosOrder(pRoot->right, pRes, index); //遍历根节点 pRes[*index] = pRoot->val; (*index)++; } } int GetTreeSize(Node* pRoot){ if (NULL == pRoot){ return 0; } return GetTreeSize(pRoot->left) + GetTreeSize(pRoot->right) + 1; } //将二叉树中每个结点值域保存到一段连续空间中返回 int* posorderTraversal(struct TreeNode* root, int* returnSize){ /*int* pRes = NULL; if (NULL == root){ return NULL; }*/ *returnSize = GetTreeSize(root); pRes = (int*)malloc(sizeof(int)*(*returnSize)); if (NULL == pRes){ assert(0); return NULL; } int index = 0; _PreOrder(root, pRes, returnSize); return pRes; }

二叉树的面试题(C++版本)

#include <iostream> using namespace std; #if 0 // 所有排序：模板 + 仿函数 void HeapAdjust(int* array, int size, int parent) { int child = parent * 2 + 1; while (child < size) { // 找左右孩子中较大的孩子 if (child+1 < size && array[child+1] > array[child]) { child += 1; } if (array[parent] < array[child]) { swap(array[parent], array[child]); parent = child; child = parent * 2 + 1; } else return; } } // 堆排序 void HeapSort(int* array, int size) { // 1. 创建堆---向下调整 // 升序---->大堆 降序---小堆 // 找倒数第一个非叶子节点 int root = ((size - 2) >> 1); for (; root >= 0; --root) HeapAdjust(array, size, root); // 2. 堆删除的思想---向下调整 int end = size - 1; while (end) { swap(array[0], array[end]); HeapAdjust(array, end, 0); --end; } } int main() { int array[] = {3,4,1,9,0,6,8,5,2,7}; HeapSort(array, sizeof(array) / sizeof(array[0])); return 0; } #endif #if 0 template<class T, class Compare> void HeapAdjust(T* array, int size, int parent, Compare com) { int child = parent * 2 + 1; while (child < size) { // 找左右孩子中较大的孩子 if (child + 1 < size && com(array[child + 1], array[child])) { child += 1; } if (com(array[child], array[parent])) { swap(array[parent], array[child]); parent = child; child = parent * 2 + 1; } else return; } } // 堆排序 template<class T, class Compare> void HeapSort(T* array, int size, Compare com) { // 1. 创建堆---向下调整 // 升序---->大堆 降序---小堆 // 找倒数第一个非叶子节点 int root = ((size - 2) >> 1); for (; root >= 0; --root) HeapAdjust(array, size, root, com); // 2. 堆删除的思想---向下调整 int end = size - 1; while (end) { swap(array[0], array[end]); HeapAdjust(array, end, 0, com); --end; } } #include <functional> int main() { int array[] = { 3, 4, 1, 9, 0, 6, 8, 5, 2, 7 }; HeapSort(array, sizeof(array) / sizeof(array[0]), less<int>()); //sort(array, array + sizeof(array) / sizeof(array[0]), greater<int>()) return 0; } #endif #include <vector> // 孩子表示法 struct BTNode { BTNode(int data) : _pLeft(nullptr) , _pRight(nullptr) , _data(data) {} BTNode* _pLeft; BTNode* _pRight; int _data; }; // A B D C E F BTNode* CreateBinTree(const vector<int>& v, int& index, const int invalid) { BTNode* pRoot = nullptr; if (index < v.size() && invalid != v[index]) { // 创建根节点pRoot pRoot = new BTNode(v[index]); // 创建pRoot的左子树 pRoot->_pLeft = CreateBinTree(v, ++index, invalid); // 创建pRoot的右子树 pRoot->_pRight = CreateBinTree(v, ++index, invalid); } return pRoot; } void Destroy(BTNode*& pRoot) { if (pRoot) { Destroy(pRoot->_pLeft); Destroy(pRoot->_pRight); delete pRoot; pRoot = nullptr; } } // 遍历：对二叉树中的每个节点进行某种操作，并且每个节点只操作一次 // 前序、中序、后序 // 操作：将节点中的值域打印 void PreOrder(BTNode* pRoot) { if (pRoot) { cout << pRoot->_data << " "; PreOrder(pRoot->_pLeft); PreOrder(pRoot->_pRight); } } #include <stack> void PreOrderNor(BTNode* pRoot) { if (nullptr == pRoot) return; stack<BTNode*> s; s.push(pRoot); while (!s.empty()) { BTNode* pCur = s.top(); s.pop(); cout << pCur->_data << " "; if (pCur->_pRight) s.push(pCur->_pRight); if (pCur->_pLeft) s.push(pCur->_pLeft); } } void InOrder(BTNode* pRoot) { if (pRoot) { InOrder(pRoot->_pLeft); cout << pRoot->_data << " "; InOrder(pRoot->_pRight); } } void InOrderNor(BTNode* pRoot) { if (nullptr == pRoot) return; stack<BTNode*> s; BTNode* pCur = pRoot; while (!s.empty() || pCur) { // 找以pRoot为根的二叉树最左侧的节点，并保存其所经路径中所有节点 while (pCur) { s.push(pCur); pCur = pCur->_pLeft; } pCur = s.top(); cout << pCur->_data << " "; s.pop(); pCur = pCur->_pRight; } } void PostOrder(BTNode* pRoot) { if (pRoot) { PostOrder(pRoot->_pLeft); PostOrder(pRoot->_pRight); cout << pRoot->_data << " "; } } void PostOrderNor(BTNode* pRoot) { if (nullptr == pRoot) return; stack<BTNode*> s; BTNode* pCur = pRoot; BTNode* pPrev = nullptr; while (!s.empty() || pCur) { // 找以pRoot为根的二叉树最左侧的节点，并保存其所经路径中所有节点 while (pCur) { s.push(pCur); pCur = pCur->_pLeft; } BTNode* pTop = s.top(); // pTop右子树不存在 // pTop右子树已经遍历 if (nullptr == pTop->_pRight || pTop->_pRight == pPrev) { cout << pTop->_data << " "; pPrev = pTop; s.pop(); } else { pCur = pTop->_pRight; } } } #include <queue> void LevelOrder(BTNode* pRoot) { if (nullptr == pRoot) return; queue<BTNode*> q; q.push(pRoot); while (!q.empty()) { BTNode* pCur = q.front(); cout << pCur->_data << " "; if (pCur->_pLeft) q.push(pCur->_pLeft); if (pCur->_pRight) q.push(pCur->_pRight); q.pop(); } } size_t Height(BTNode* pRoot) { if (nullptr == pRoot) return 0; size_t leftHeight = Height(pRoot->_pLeft); size_t rightHeight = Height(pRoot->_pRight); return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; } size_t GetBTreeNode(BTNode* pRoot) { if (nullptr == pRoot) return 0; return GetBTreeNode(pRoot->_pLeft) + GetBTreeNode(pRoot->_pRight) + 1; } size_t GetLeafNode(BTNode* pRoot) { if (nullptr == pRoot) return 0; if (nullptr == pRoot->_pLeft && nullptr == pRoot->_pRight) { return 1; } return GetLeafNode(pRoot->_pLeft) + GetLeafNode(pRoot->_pRight); } size_t GetKLevelNodeCount(BTNode* pRoot, size_t K) { if (nullptr == pRoot || 0 == K) return 0; if (1 == K) return 1; return GetKLevelNodeCount(pRoot->_pLeft, K - 1) + GetKLevelNodeCount(pRoot->_pRight, K - 1); } BTNode* GetParent(BTNode* pRoot, BTNode* pNode) { if (nullptr == pRoot || pRoot == pNode) return nullptr; if (pRoot->_pLeft == pNode || pRoot->_pRight == pNode) return pRoot; BTNode* pParent = GetParent(pRoot->_pLeft, pNode); if (pParent) return pParent; return GetParent(pRoot->_pRight, pNode); } // 前序 中序 BTNode* _ReBuildTree(const vector<int>& pre, int& index, const vector<int>& In, int left, int right) { if (left >= right) return nullptr; // 1. 从前序遍历结果中获取根节点 BTNode* pRoot = new BTNode(pre[index]); // 2. 从中序遍历结果确认根的左右子树 size_t InIdx = left; while (In[InIdx] != pre[index]) InIdx++; // [left, InIdx) // [InIdx+1, right) if (left < InIdx) pRoot->_pLeft = _ReBuildTree(pre, ++index, In, left, InIdx); if (index+1 < right) pRoot->_pRight = _ReBuildTree(pre, ++index, In, InIdx + 1, right); return pRoot; } BTNode* ReBuildTree(const vector<int>& pre, const vector<int>& In) { int index = 0; return _ReBuildTree(pre, index, In, 0, In.size()); } int main() { vector<int> v{ 1, 2, 3, -1,-1,-1,4, 5, -1,-1,6 }; int index = 0; BTNode* pRoot = CreateBinTree(v, index, -1); PreOrder(pRoot); PreOrderNor(pRoot); cout << endl; InOrder(pRoot); InOrderNor(pRoot); cout << endl; PostOrder(pRoot); PostOrderNor(pRoot); Destroy(pRoot); vector<int> Pre{ 1, 2, 3, 4, 5, 6 }; vector<int> In{3,2,1,5,4,6}; BTNode* pNewRoot = ReBuildTree(Pre, In); return 0; }