二叉树进阶面试题
1.根据二叉树创建字符串
你需要采用前序遍历的方式,将一个二叉树转换成一个由括号和整数组成的字符串。
空节点则用一对空括号 “()” 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
void _tree2str(struct TreeNode* t,char* ptr)
{
if(t == NULL)
return;
char buff[12] = {'\0'};
sprintf(buff,"%d",t->val);//类似于itoa为了将数字转换为字符
strcat(ptr,buff);
if(t -> left == NULL)
{
if(t->right == NULL)
{
return;
}
else
{
strcat(ptr,"()");
}
}
else
{
strcat(ptr,"(");
_tree2str(t->left,ptr);
strcat(ptr,")");
}
if(t->right == NULL)
{
return;
}
else
{
strcat(ptr,"(");
_tree2str(t->right,ptr);
strcat(ptr,")");
}
}
char* tree2str(struct TreeNode* t) {
char* ptr = (char*)malloc(1024*1024);
_tree2str(t, ptr);
return ptr;
}
2.二叉树的最近公共祖先
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
int FindNode(struct TreeNode* dest,struct TreeNode* src)
{
if(dest == NULL) return 0;
if(dest == src) return 1;
else if(FindNode(dest->left,src) == 1) return 1;
else if(FindNode(dest->right,src) == 1) return 1;
else return 0;
}
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
if(root == NULL) return NULL;
if(p == root || q == root) return root;
int pInleft = FindNode(root->left,p);
int qInleft = FindNode(root->left,q);
if(pInleft == 1 && qInleft == 1)
return lowestCommonAncestor(root->left,p,q);
else if(pInleft == 0 && qInleft == 0)
return lowestCommonAncestor(root->right,p,q);
else
return root;
}
3.二叉搜索树与双向链表
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。
TreeNode* prev = NULL;//全局变量,c语言不利于引用
void _Convert(TreeNode* cur)
{
if(cur == NULL) return;
_Convert(cur->left);
cur->left = prev;
if(prev)
prev->right = cur;
prev = cur;
_Convert(cur->right);
}
TreeNode* Convert(TreeNode* pRootOfTree)
{
if(pRootOfTree == NULL) return NULL;
_Convert(pRootOfTree);
TreeNode* head = pRootOfTree;
while(head && head->left)
{
head = head -> left;
}
return head;
}
4.根据一棵树的前序遍历与中序遍历构造二叉树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* _buildTree(int* preorder, int* index, int* inorder, int start, int end)
{
if (start > end) return NULL;
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = preorder[(*index)];
++(*index);
if (start == end)
{
root->left = NULL;
root->right = NULL;
return root;
}
int rootindex = start;
while (rootindex <= end)
{
if (root->val == inorder[rootindex])
{
break;
}
else
{
++(rootindex);
}
}
root->left = _buildTree(preorder, index, inorder, start, rootindex - 1);
root->right = _buildTree(preorder, index, inorder, rootindex + 1,end);
return root;
}
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {
int index = 0;
return _buildTree(preorder, &index, inorder, 0, inorderSize - 1);
}
5. 根据一棵树的中序遍历与后序遍历构造二叉树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* _buildTree(int* postorder, int* index, int* inorder, int start, int end)
{
if (start > end) return NULL;
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = postorder[(*index)];
--(*index);
if (start == end)
{
root->left = NULL;
root->right = NULL;
return root;
}
int rootindex = start;
while (rootindex <= end)
{
if (root->val == inorder[rootindex])
{
break;
}
else
{
++(rootindex);
}
}
root->right = _buildTree(postorder, index, inorder, rootindex + 1,end);
root->left = _buildTree(postorder, index, inorder, start, rootindex - 1);
return root;
}
struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize) {
int index = postorderSize-1;
return _buildTree(postorder, &index, inorder, 0, inorderSize - 1);
}
6. 二叉树的前序遍历,非递归迭代实现
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
typedef struct TreeNode* STDataType;
typedef struct Stack
{
STDataType* _a;
int _top;
int _capacity;
}Stack;
void StackInit(Stack* ps)
{
assert(ps);
ps->_a = NULL;
ps->_capacity = 0;
ps->_top = 0;
}
void StackDestory(Stack* ps)
{
assert(ps);
free(ps->_a);
ps->_a = NULL;
ps->_capacity = 0;
ps->_top = 0;
}
void StackPush(Stack* ps, STDataType x)
{
assert(ps);
if (ps->_top == ps->_capacity)
{
size_t newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
ps->_a = (STDataType*)realloc(ps->_a, sizeof(STDataType)*newcapacity);
assert(ps->_a != NULL);
ps->_capacity = newcapacity;
}
ps->_a[ps->_top] = x;
ps->_top++;
}
void StackPop(Stack* ps)
{
assert(ps && ps->_top > 0);
--ps->_top;
}
STDataType StackTop(Stack* ps)
{
assert(ps && ps->_top > 0);
return ps->_a[ps->_top - 1];
}
int StackEmpty(Stack* ps)
{
assert(ps);
return ps->_top == 0 ? 0 : 1;
}
int StackSize(Stack* ps)
{
assert(ps);
return ps->_top;
}
//上面模拟实现了栈,c没有库所以只能自己实现
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
int size = 0;
int i = 0;
Stack st;
StackInit(&st);
struct TreeNode* cur = root;
while(cur != NULL || StackEmpty(&st) != 0)//为了求出二叉树有多少结点,为开辟空间做准备
{
while(cur != NULL)
{
size++;
StackPush(&st,cur);
cur = cur -> left;
}
struct TreeNode* top = StackTop(&st);
StackPop(&st);
cur = top -> right;
}
cur = root;
int* arr = (int*)malloc(sizeof(int)*size);
while(cur != NULL || StackEmpty(&st) != 0)
{
while(cur != NULL)
{
arr[i++] = cur->val;
StackPush(&st,cur);
cur = cur -> left;
}
struct TreeNode* top = StackTop(&st);
StackPop(&st);
cur = top -> right;
}
*returnSize = i;
return arr;
}
7.二叉树中序遍历 ,非递归迭代实现。
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
int size = 0;
int i = 0;
Stack st;
StackInit(&st);
struct TreeNode* cur = root;
while(cur != NULL || StackEmpty(&st) != 0)
{
while(cur != NULL)
{
size++;
StackPush(&st,cur);
cur = cur -> left;
}
struct TreeNode* top = StackTop(&st);
StackPop(&st);
cur = top -> right;
}
cur = root;
int* arr = (int*)malloc(sizeof(int)*size);
while(cur != NULL || StackEmpty(&st) != 0)
{
while(cur != NULL)
{
StackPush(&st,cur);
cur = cur -> left;
}
struct TreeNode* top = StackTop(&st);
arr[i++] = top->val;
StackPop(&st);
cur = top -> right;
}
*returnSize = i;
return arr;
}