二叉樹經典OJ
- 翻轉二叉樹
- 單值二叉樹
- 根據二叉樹創建字串
- 二叉樹層序遍歷
- 二叉樹的最近公共祖先
- 二叉搜索樹轉換為鏈表
- 根據二叉樹前序中序遍歷構造二叉樹
翻轉二叉樹
鏈接: https://leetcode-cn.com/problems/invert-binary-tree/.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* invertTree(struct TreeNode* root)
{
if(root == NULL)
return NULL;
struct TreeNode* p = NULL;
p = root->left;
root->left = root->right;
root->right = p;
root->left = invertTree(root->left);
root->right = invertTree(root->right);
return root;
}
單值二叉樹
鏈接: https://leetcode-cn.com/problems/univalued-binary-tree/submissions/.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool isUnivalTree(struct TreeNode* root)
{
if(root == NULL)
return true;
if(root->left && root->left->val != root->val)
return false;
if(root->right && root->right->val != root->val)
return false;
return isUnivalTree(root->left) && isUnivalTree(root->right);
}
根據二叉樹創建字串
鏈接: https://leetcode-cn.com/problems/construct-string-from-binary-tree/.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
void _tree2str(struct TreeNode* t, char* str)
{
if(t == NULL)
return;
char buf[10] = {0};
sprintf(buf, "%d", t->val);//將第一個元素轉換成整型輸入到buf中
strcat(str, buf);
if(t->left == NULL)
{
if(t->right == NULL)
return;
else
strcat(str, "()");
}
else{
strcat(str, "(");
_tree2str(t->left, str);
strcat(str,")");
}
if(t->right == NULL)
return;
else{
strcat(str, "(");
_tree2str(t->right, str);
strcat(str, ")");
}
}
char * tree2str(struct TreeNode* t)
{
int n = 100000;
char* str = (char*)malloc(sizeof(char)* n);
str[0] = '\0';
_tree2str(t, str);
return str;
}
二叉樹層序遍歷
鏈接: https://leetcode-cn.com/problems/binary-tree-level-order-traversal/submissions/.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
int maxDepth(struct TreeNode* t)//求樹高度
{
if(t == NULL)
return 0;
int left_h = maxDepth(t->left);
int right_h = maxDepth(t->right);
return (left_h > right_h ? left_h : right_h) + 1;
}
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes)
{
if(root == NULL)
{
*returnSize = 0;
return NULL;
}
int max_level = maxDepth(root);
*returnSize = max_level;//二維陣列的行
int **levelOrder = (int**)malloc(sizeof(int*) * max_level);//申請二級指標指向一個含有三個指標的陣列
*returnColumnSizes = (int*)malloc(sizeof(int) * max_level);//每一行中列的個數
//開始層次遍歷
struct TreeNode* q1[1000],* q2[1000];//使用佇列開始層次遍歷
int q1_size = 0, q2_size = 0;
q1[0] = root;//佇列1放入根節點
q1_size++;
int level = 0;//從頂層開始
while(level < max_level)//回圈的次數為二維陣列行的大小
{
levelOrder[level] = (int*)malloc(sizeof(int) * q1_size);//給每一行申請空間
for(int i = 0; i<q1_size; ++i)
levelOrder[level][i] = q1[i]->val;//賦值
(*returnColumnSizes)[level] = q1_size;//第一行的列的個數為佇列1的大小
for(int i = 0; i<q1_size; ++i)
{
if(q1[i]->left != NULL)
q2[q2_size++] = q1[i]->left;
if(q1[i]->right != NULL)
q2[q2_size++] = q1[i]->right;
}
memcpy(q1, q2, sizeof(struct TreeNode*) * q2_size);
q1_size = q2_size;
q2_size = 0;
level++;
}
return levelOrder;
}
二叉樹的最近公共祖先
鏈接: https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/submissions/.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool findNode(struct TreeNode* root, struct TreeNode* n)//尋找節點
{
if(root == NULL)
return false;
if(root == n)
return true;
return findNode(root->left, n) || findNode(root->right,n);
}
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q)
{
if(root == NULL)
return NULL;
if(p == root || q == root)
return root;
bool pInleft, pInright, qInleft, qInright;
if(findNode(root->left, p))
{
pInleft = true;
pInright = false;
}
else
{
pInleft = false;
pInright = true;
}
if(findNode(root->left,q))
{
qInleft = true;
qInright = false;
}
else{
qInright = true;
qInleft = false;
}
if(qInleft && pInleft)//兩個都在左樹部分，則在左樹找
return lowestCommonAncestor(root->left, p, q);
if(qInright && pInright)//同上
return lowestCommonAncestor(root->right, p, q);
return root;
}
二叉搜索樹轉換為鏈表
鏈接: https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&tqId=11179&rp=1&ru=%2Factivity%2Foj&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey.
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
*
* @param pRootOfTree TreeNode類
* @return TreeNode類
*/
//二叉搜索樹的中序遍歷就是由小到大的順序排序
void ConvertList(struct TreeNode* t, struct TreeNode** pre)//轉換為鏈表
{
if(t == NULL)
return;
ConvertList(t->left,pre);
t->left = *pre;
if(*pre != NULL)
(*pre)->right = t;
*pre = t;
ConvertList(t->right, pre);
}
struct TreeNode* Convert(struct TreeNode* pRootOfTree )
{
if(pRootOfTree == NULL)
return NULL;
struct TreeNode* pre = NULL;
ConvertList(pRootOfTree, &pre);
struct TreeNode* pHead = pre;
while(pHead->left != NULL)//將指標從最后一位移到第一位
pHead = pHead->left;
return pHead;
}
根據二叉樹前序中序遍歷構造二叉樹
鏈接: https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/.
之前寫過一篇這類專題：根據前中后序創建二叉樹
本題解法:`
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize)
{
if(preorderSize == 0)
return NULL;
//中序中找根的位置
int k = 0;
while(inorder[k] != preorder[0])
k++;
struct TreeNode* t = (struct TreeNode*)malloc(sizeof(struct TreeNode));
t->val = inorder[k];
t->left = buildTree(preorder+1, k, inorder, k);
t->right = buildTree(preorder+k+1, preorderSize-k-1, inorder+k+1, preorderSize-k-1);
return t;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/263313.html
標籤：其他