Leetcode -1

Leetcode -94.二叉树的中序遍历

题目：给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：
输入：root = [1, null, 2, 3]
输出：[1, 3, 2]

示例 2：
输入：root = []
输出：[]

示例 3：
输入：root = [1]
输出：[1]

提示：
树中节点数目在范围[0, 100] 内

• 100 <= Node.val <= 100

思路：二叉树的中序遍历，化为子问题先遍历当前根的左子树，再打印当前根的值，最后遍历当前根的右子树；

		void Inorder(struct TreeNode* root, int* a, int* pos)
		{
		    if (root == NULL)
		        return;
		
		    //先递归当前根的左子树；再将当前根的 val 存放到数组中；最后递归当前根的右子树
		    Inorder(root->left, a, pos);
		    a[(*pos)++] = root->val;
		    Inorder(root->right, a, pos);
		}
		
		
		
		int* inorderTraversal(struct TreeNode* root, int* returnSize)
		{
		    //开辟一个返回中序遍历的数组，pos记录数组的长度
		    int* ret = (int*)malloc(sizeof(int) * 100);
		    int pos = 0;
		
		    //进入中序遍历
		    Inorder(root, ret, &pos);
		    *returnSize = pos;
		    return ret;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Leetcode -145.二叉树的后序遍历

题目：给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例 1：
输入：root = [1, null, 2, 3]
输出：[3, 2, 1]

示例 2：
输入：root = []
输出：[]

示例 3：
输入：root = [1]
输出：[1]

提示：
树中节点的数目在范围[0, 100] 内

• 100 <= Node.val <= 100

思路：二叉树的后序遍历，化为子问题先遍历当前根的左子树，再遍历当前根的右子树，最后打印当前根的值；

		void Postorder(struct TreeNode* root, int* a, int* pos)
		{
		    if (root == NULL)
		        return;
		
		    //先递归当前根的左子树；再递归当前根的右子树；最后将当前根的 val 存放到数组中
		    Postorder(root->left, a, pos);
		    Postorder(root->right, a, pos);
		    a[(*pos)++] = root->val;
		}
		
		
		int* postorderTraversal(struct TreeNode* root, int* returnSize)
		{
		    //开辟返回的数组
		    int* ret = (int*)malloc(sizeof(int) * 100);
		    int pos = 0;
		
		    //进入后序遍历
		    Postorder(root, ret, &pos);
		    *returnSize = pos;
		    return ret;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23