力扣LeetCode经典算法从上到下打印二叉树

学习数据结构与算法过程中的心得体会以及知识点的整理&＃xff0c;方便我自己查找&＃xff0c;也希望可以和大家一起交流。

—— 从上到下打印二叉树 ——

1.题目描述

第一题&＃xff1a;从上到下打印出二叉树的每个节点&＃xff0c;同一层的节点按照从左到右的顺序打印。
第二题&＃xff1a;从上到下按层打印二叉树&＃xff0c;同一层的节点按从左到右的顺序打印&＃xff0c;每一层打印到一行。
第三题&＃xff1a;请实现一个函数按照之字形顺序打印二叉树&＃xff0c;即第一行按照从左到右的顺序打印&＃xff0c;第二层按照从右到左的顺序打印&＃xff0c;第三行再按照从左到右的顺序打印&＃xff0c;其他行以此类推。

示例&＃xff1a;

第一题&＃xff1a;
输入&＃xff1a;
[3,9,20,null,null,15,7]

3/ \9 20/ \15 7


输出&＃xff1a;

[3,9,20,15,7]

第二题&＃xff1a;
输入&＃xff1a;
[3,9,20,null,null,15,7]

3/ \9 20/ \15 7


输出&＃xff1a;

[[3],[9,20],[15,7]
]


第三题&＃xff1a;

输入&＃xff1a;
[3,9,20,null,null,15,7]

3/ \9 20/ \15 7


输出&＃xff1a;

[[3],[20,9],[15,7]
]


2.代码

第一题&＃xff1a;
c

/*** 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().*/#define MAX_SIZE 1200
int* levelOrder(struct TreeNode* root, int* returnSize){if(root &＃61;&＃61; NULL){*returnSize &＃61; 0;return root;}struct TreeNode *Queue[MAX_SIZE];int fornt &＃61;-1,rear&＃61;-1;int len&＃61;0;struct TreeNode *p;int *arr&＃61;(int *)malloc(sizeof(int)*MAX_SIZE);Queue[&＃43;&＃43;rear]&＃61;root;while(fornt<rear){p&＃61;Queue[&＃43;&＃43;fornt];arr[len&＃43;&＃43;]&＃61;p->val;if(p->left)Queue[&＃43;&＃43;rear]&＃61;p->left;if(p->right)Queue[&＃43;&＃43;rear]&＃61;p->right;}*returnSize&＃61;len;return arr;
}


第二题&＃xff1a;
c

/*** 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().*/#define MAX_SIZE 1200
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes)
{if(root &＃61;&＃61; NULL){*returnSize &＃61; 0;return NULL;}struct TreeNode *Node[MAX_SIZE];int **nums &＃61; (int **)malloc(sizeof(int *)*MAX_SIZE);*returnColumnSizes &＃61; (int *)malloc(sizeof(int*)*MAX_SIZE);int fornt &＃61; 0,rear &＃61; 0,line &＃61; 0,column &＃61; 0,count &＃61; 0,k &＃61; 1;Node[rear&＃43;&＃43;] &＃61; root;nums[line] &＃61; (int *)malloc(sizeof(int)*k); (*returnColumnSizes)[line] &＃61; k;while(fornt < rear){struct TreeNode* temp &＃61; Node[fornt&＃43;&＃43;]; nums[line][column&＃43;&＃43;] &＃61; temp->val;if(temp->left){Node[rear&＃43;&＃43;] &＃61; temp->left;count&＃43;&＃43;;}if(temp->right){Node[rear&＃43;&＃43;] &＃61; temp->right;count&＃43;&＃43;;}k--;if(k &＃61;&＃61; 0){k &＃61; count;count &＃61; 0;column &＃61; 0;line&＃43;&＃43;;nums[line] &＃61; (int*)malloc(sizeof(int)*k);(*returnColumnSizes)[line] &＃61; k;} }*returnSize &＃61; line;return nums;
}


第三题&＃xff1a;
c

/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/#define MAX_SIZE 1200
void FlipData(int **ans, int line, int column)
{int left &＃61; 0;int right &＃61; column - 1;while (left < right) {int tmp &＃61; ans[line][right];ans[line][right] &＃61; ans[line][left];ans[line][left] &＃61; tmp;left&＃43;&＃43;;right--;}return;
}
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){if(root &＃61;&＃61; NULL){ *returnSize &＃61; 0;return NULL;}struct TreeNode *Node[MAX_SIZE];int **nums &＃61; (int **)malloc(sizeof(int *)*MAX_SIZE);*returnColumnSizes &＃61; (int *)malloc(sizeof(int*)*MAX_SIZE);//fornt&＃xff1a;队列头坐标 rear&＃xff1a;队列尾坐标 line&＃xff1a;数组行下标 column&＃xff1a;数组列下标 count:每层节点数量int fornt &＃61; 0,rear &＃61; 0,line &＃61; 0,column &＃61; 0,count &＃61; 0,k &＃61; 1;Node[rear&＃43;&＃43;] &＃61; root;nums[line] &＃61; (int *)malloc(sizeof(int)*k); (*returnColumnSizes)[line] &＃61; k;while(fornt < rear){struct TreeNode* temp &＃61; Node[fornt&＃43;&＃43;]; nums[line][column&＃43;&＃43;] &＃61; temp->val;if(temp->left){Node[rear&＃43;&＃43;] &＃61; temp->left;count&＃43;&＃43;;}if(temp->right){Node[rear&＃43;&＃43;] &＃61; temp->right;count&＃43;&＃43;;}k--;if(k &＃61;&＃61; 0){if((line-1) % 2 &＃61;&＃61;0)FlipData(nums,line,column);k &＃61; count;count &＃61; 0; column &＃61; 0;line&＃43;&＃43;;nums[line] &＃61; (int*)malloc(sizeof(int)*k);(*returnColumnSizes)[line] &＃61; k;} }*returnSize &＃61; line;return nums;
}


这三道题都是二叉树的层次搜索&＃xff0c;知识输出的形式不同&＃xff0c;程序的主要部分是差不多的。