代碼隨想錄——二叉樹（一）

文章目錄

- - 二叉樹遍歷
  - - 先序遍歷
    - 中序遍歷
    - 后序遍歷
    - 層序遍歷
    - 層序遍歷Ⅱ
    - 二叉樹的右視圖
    - 二叉樹的層平均值
    - N插樹的層序遍歷
    - 在每個樹行中找最大值
    - 填充每個節點的下一個右側節點指針
    - 填充每個節點的下一個右側節點指針 II

二叉樹遍歷

先序遍歷

二叉樹先序遍歷

遞歸形式

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/
int ans[100];
int cnt=0;
void PreOrder(struct TreeNode* root){if(root==NULL)return;ans[cnt++]=root->val;PreOrder(root->left);PreOrder(root->right);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {cnt=0;PreOrder(root);*returnSize=cnt;return ans;
}

非遞歸形式（迭代法）

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/int* preorderTraversal(struct TreeNode* root, int* returnSize) {int *ans=malloc(sizeof(int)*100);*returnSize=0;if(root==NULL)return ans;struct TreeNode* st[100];struct TreeNode* node=root;int top=0;while(top>0||node!=NULL){while(node!=NULL){ans[(*returnSize)++]=node->val;st[top++]=node;node=node->left;}node=st[--top]->right;}return ans;
}

中序遍歷

二叉樹中序遍歷

遞歸

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/
void Inorder(struct TreeNode* root,int *ans,int *cnt){if(root==NULL)return;Inorder(root->left,ans,cnt);ans[(*cnt)++]=root->val;Inorder(root->right,ans,cnt);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {int *ans=malloc(sizeof(int)*100);int cnt=0;Inorder(root,ans,&cnt);*returnSize=cnt;return ans;
}

非遞歸

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/
int* inorderTraversal(struct TreeNode* root, int* returnSize) {int *ans=malloc(sizeof(int)*100);*returnSize=0;if(root==NULL)return ans;struct TreeNode *st[100];struct TreeNode *node=root;int top=0;while(top>0||node!=NULL){while(node!=NULL){st[top++]=node;node=node->left;}node=st[--top];ans[(*returnSize)++]=node->val;node=node->right;}return ans;
}

后序遍歷

二叉樹后序遍歷

遞歸

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/
void PostOrder(struct TreeNode* root,int *ans,int *cnt){if(root==NULL)return;PostOrder(root->left,ans,cnt);PostOrder(root->right,ans,cnt);ans[(*cnt)++]=root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize) {int *ans=malloc(sizeof(int)*100);int cnt=0;PostOrder(root,ans,&cnt);*returnSize=cnt;return ans;
}

非遞歸

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/int* postorderTraversal(struct TreeNode* root, int* returnSize) {int *ans=malloc(sizeof(int)*100);*returnSize=0;if(root==NULL)return ans;struct TreeNode* st[100];struct TreeNode* node=root;struct TreeNode* pre=NULL;int top=0;while(top>0||node!=NULL){while(node!=NULL){st[top++]=node;node=node->left;}node=st[--top];if(node->right==NULL||node->right==pre){ans[(*returnSize)++]=node->val;pre=node;node=NULL;}else{st[top++]=node;node=node->right;}}return ans;
}

層序遍歷

二叉樹層序遍歷

/*** 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** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {//returnSize——二叉樹高度//returnColumnSizes——每層的節點數struct TreeNode *queue[2000];int front=0;int tail=0;int **ans=malloc(sizeof(int*)*2000);*returnColumnSizes=malloc(sizeof(int)*2000);queue[front++]=root;*returnSize=0;if(root==NULL)return ans;while(front>tail){int t=front;int cnt=0;//記錄該層節點個數ans[*returnSize]=malloc(sizeof(int)*(t-tail));for(tail;tail<t;tail++){//遍歷當前層的節點，并將下一層節點放入struct TreeNode* node=queue[tail];ans[*returnSize][cnt++]=node->val;if(node->left)queue[front++]=node->left;if(node->right)queue[front++]=node->right;}(*returnColumnSizes)[(*returnSize)++]=cnt;}return ans;
}

層序遍歷Ⅱ

二叉樹層序遍歷Ⅱ

思路：與上面的思路類似，只是在后面把結果反轉

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
int** levelOrderBottom(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {if (root == NULL) {*returnSize = 0;*returnColumnSizes = NULL;return NULL;}struct TreeNode** queue = malloc(sizeof(struct TreeNode*) * 2000); // 動態分配隊列int front = 0, tail = 0;int** ans = malloc(sizeof(int*) * 2000); // 存儲層次遍歷結果*returnColumnSizes = malloc(sizeof(int) * 2000); // 存儲每層的節點數*returnSize = 0;queue[front++] = root; // 根節點入隊while (front > tail) {int levelSize = front - tail; // 當前層的節點數ans[*returnSize] = malloc(sizeof(int) * levelSize); // 分配當前層的存儲空間(*returnColumnSizes)[*returnSize] = levelSize; // 記錄當前層的節點數for (int i = 0; i < levelSize; i++) {struct TreeNode* node = queue[tail++];ans[*returnSize][i] = node->val; // 存儲當前節點的值if (node->left) queue[front++] = node->left; // 左子節點入隊if (node->right) queue[front++] = node->right; // 右子節點入隊}(*returnSize)++; // 處理完一層}// 反轉結果int** res = malloc(sizeof(int*) * (*returnSize));for (int i = 0; i < *returnSize; i++) {int level = *returnSize - 1 - i;res[i] = ans[level]; // 直接使用 ans 的內存，避免重復分配}// 反轉 returnColumnSizesfor (int i = 0; i < *returnSize / 2; i++) {int temp = (*returnColumnSizes)[i];(*returnColumnSizes)[i] = (*returnColumnSizes)[*returnSize - 1 - i];(*returnColumnSizes)[*returnSize - 1 - i] = temp;}free(queue); // 釋放隊列內存return res;
}

二叉樹的右視圖

題目鏈接

思路：其實就是取每一層的最右邊節點的值，在層序遍歷時只保存最后一個值就行了。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/int* rightSideView(struct TreeNode* root, int* returnSize) {
//其實就是取每一層最右邊的值struct TreeNode *queue[100];int *ans=malloc(sizeof(int)*100);struct TreeNode* node=root;*returnSize=0;int front=0;int tail=0;queue[front++]=node;if(root==NULL)return ans;while(front>tail){int t=front;while(tail<t){node=queue[tail++];if(node->left)queue[front++]=node->left;if(node->right)queue[front++]=node->right;}ans[(*returnSize)++]=queue[t-1]->val;}    return ans;
}

二叉樹的層平均值

題目鏈接

思路：層次遍歷的時候計算計算一下平均值

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/
double* averageOfLevels(struct TreeNode* root, int* returnSize) {double *ans=malloc(sizeof(int)*10005);struct TreeNode* queue[10005];int front=0,tail=0;struct TreeNode *node=root;*returnSize=0;queue[front++]=node;if(root==NULL)return ans;while(front>tail){double avg=0;int t=front;double num=front-tail;//當前層節點數while(tail<t){node=queue[tail++];if(node->left)queue[front++]=node->left;if(node->right)queue[front++]=node->right;avg+=(double)node->val;}avg/=num;ans[(*returnSize)++]=avg;}return ans;
}

N插樹的層序遍歷

題目鏈接

思路：paper tiger，和二叉樹的層次遍歷的區別在于訪問孩子節點的方式不同

/*** Definition for a Node.* struct Node {*     int val;*     int numChildren;*     struct Node** children;* };*//*** 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** levelOrder(struct Node* root, int* returnSize, int** returnColumnSizes) {struct Node* queue[10005];int front=0,tail=0;int **ans=malloc(sizeof(int*)*1000);struct Node* node=root;*returnSize=0;*returnColumnSizes=malloc(sizeof(int)*1000);if(root==NULL)return ans;queue[front++]=node;while(front>tail){int len=front-tail;ans[*returnSize]=malloc(sizeof(int)*len);int cnt=0;//保存訪問到該層的第幾個節點int t=front;while(tail<t){node=queue[tail++];ans[*returnSize][cnt++]=node->val;if(node->numChildren>0){//將孩子節點放入隊列    int n=node->numChildren;for(int i=0;i<n;i++){queue[front++]=(node->children)[i];}}}(*returnColumnSizes)[(*returnSize)++]=len;}return ans;
}

在每個樹行中找最大值

題目鏈接

思路：由上面求平均值改寫，將求平均值的邏輯改為求最大值就行啦! >v<

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/
int* largestValues(struct TreeNode* root, int* returnSize) {int *ans=malloc(sizeof(int)*10005);struct TreeNode* queue[10005];int front=0,tail=0;struct TreeNode *node=root;*returnSize=0;queue[front++]=node;if(root==NULL)return ans;while(front>tail){int Max=queue[tail]->val;int t=front;while(tail<t){node=queue[tail++];if(node->left)queue[front++]=node->left;if(node->right)queue[front++]=node->right;if(node->val>Max)Max=node->val;}ans[(*returnSize)++]=Max;}return ans;
}

填充每個節點的下一個右側節點指針

題目鏈接

思路：還是二叉樹層序遍歷的思路，每一層的節點用next指針連接就好，不要忘記邊界哦。

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *left;*     struct Node *right;*     struct Node *next;* };*/struct Node* connect(struct Node* root) {//實際上只需要填充next指針即可struct Node* queue[5000];int front=0;int tail=0;if(root==NULL)return root;queue[front++]=root;while(front>tail){int t=front;while(tail<t){if(queue[tail]->left)queue[front++]=queue[tail]->left;if(queue[tail]->right)queue[front++]=queue[tail]->right;if(tail<t-1)queue[tail]->next=queue[tail+1];else queue[tail]->next=NULL;tail++;}}return root;;
}

填充每個節點的下一個右側節點指針 II

思路：直接用上一題代碼就行了，但是要把隊列內存擴大。。。hahaha

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *left;*     struct Node *right;*     struct Node *next;* };*/struct Node* connect(struct Node* root) {struct Node* queue[6005];int front=0;int tail=0;if(root==NULL)return root;queue[front++]=root;while(front>tail){int t=front;while(tail<t){if(queue[tail]->left)queue[front++]=queue[tail]->left;if(queue[tail]->right)queue[front++]=queue[tail]->right;if(tail<t-1)queue[tail]->next=queue[tail+1];else queue[tail]->next=NULL;tail++;}}return root;;
}