【LeetCode】144.二叉树的前序遍历
题目描述.
思路分析.
- 思路很简单，专门写一个前序遍历的函数，写法也是前序遍历的写法，这里在函数传参的时候加个应用
代码详解.
C++版本
class Solution { private: void preOrder(TreeNode* root, vector<int> &ret) { if(root == NULL) return; ret.push_back(root->val); preOrder(root->left,ret); preOrder(root->right,ret); } public: vector<int> preorderTraversal(TreeNode* root) { vector<int> ret; preOrder(root,ret); return ret; } };
C语言版本（递归算法展开图）
看完C++版本是不是觉得这道题很简单，我再补充一个C语言版本的，我们来玩玩指针✒
//前序遍历 void PreOrder(struct TreeNode* root, int* a, int* pi) { if(!root) return; a[(*pi)++] = root->val; PreOrder(root->left,a,pi); PreOrder(root->right,a,pi); } //求解二叉树大小 int TreeSize(struct TreeNode* root){ if(!root) return 0; return TreeSize(root->left) + TreeSize(root->right) + 1; } int* preorderTraversal(struct TreeNode* root, int* returnSize){ //数组大小（输出型参数） //1.获取当前二叉树大小 *returnSize = TreeSize(root); //2.根据二叉树大小动态开辟数组存放遍历序列 int* a = (int *)malloc(sizeof(int) * (*returnSize)); //3.封装前序遍历 int i = 0; PreOrder(root,a,&i); return a; }
- 可以看到，对于C语言版本的代码看起来即比较冗余和复杂了，因为C语言不像C++那样有现成的STL库，因此有些东西就需要自己去造轮子了，所以对于二叉树前中后序的非递归写法我也会使用C++来实现，后续补充。。。
- 好，我们来看一下本题的C语言写法，和C++给出的主接口函数不一样的地方是在多了一个【
returnSize】的指针，而且返回值也是一个指针，哪有同学问这是啥，其实在C语言的很多代码中有个returnSize是很正常的，因为像LeetCode这种接口型的OJ题它后台内部是有代码写好了会调用你写好的这个接口函数，一般来说他会去获取你这个数组的大小，但是呢这里的返回值是【int*】，也就是一个数组，C语言还可以返回结构体，但是比较麻烦，因此这个【returnSize】其实是外界用来获取你函数中算出来的数组大小的，而且他那里传入的是一个地址，所以在函数内部你可以通过【解引用】的方式来修改这个大小 - 因此首先我们先去写了一个函数获取传进来的根节点所在的这棵树的大小，使用解引用这个指针变量来接受，这样外界就可以轻而易举地获取到你这个大小了。==指针接收地址这一块很重要，后面我们还要讲到==
*returnSize = TreeSize(root);
- 有了这棵树的大小，我们就需要根据这个大小去开辟出存放二叉树遍历序列的数组了，这里当然是使用malloc来开辟，但是对于C++来说，只需要使用vector这个顺序表就可以了，它会自动扩容的。
- 在开辟出这个数组后，我们就可以去打印出前序遍历的序列了，我这里再说一个错误的示范
void PreOrder(struct TreeNode* root, int* a, int i) { if(!root) return; a[i++] = root->val; PreOrder(root->left,a,i); PreOrder(root->right,a,i); }
- 可以看到上面我对于最后一个参数我使用的是指针，这个是用来遍历这个数组的，用来存放数据，但是对于这样的写法却存在一定的问题，我们首先提交看看
- 可以看到，通过是通过了，但是呢却出现了一些小问题，我们通过画算法图来看看
- 可以看到，对于这种结构的树，不会有问题，这就是有些案例可以通过的原因
- 我们再来看看另一种
- 可以看到，对于这种结构的树就会出现问题，从算法图可以看出，因为在这个递归的过程中内部形参i的改变不会影响外部的改变，因此在递归完左子树时虽然
i == 2，但是在回到根节点后当前层的【i】在放入1后即为1。然后来到root->right就会在i == 1的位置上放值，但是这个地方在左子树递归的时候就放了【2】，若是再放【3】的话就会造成覆盖。 - 此时就会形成一个 i 回退的现象，所以这就是上面题目给出的错误案例中为什么会出现这么大一个==随机值==的原因了，因为在
i == 2这个位置上并没有添加进值，所以是一个无符号整型的随机值 - 因此想要真正通过形参的改变影响实参，我们就需要用到【指针接收地址】的思想，就想下面这样
void PreOrder(struct TreeNode* root, int* a, int* pi) { if(!root) return; a[(*pi)++] = root->val; PreOrder(root->left,a,pi); PreOrder(root->right,a,pi); }
- 而且在主函数中还得传入i的地址才行
PreOrder(root,a,&i);
- 这样提交就可以通过全部的测试案例了
【LeetCode】94.二叉树的中序遍历
题目描述.
思路分析.
- 中序和前序也是一样，换一下根结点放入数组的时机即可
代码详解.
C++版本
class Solution { private: void InOrder(TreeNode* root, vector<int>& ret) { if(root == NULL) return; InOrder(root->left, ret); ret.push_back(root->val); InOrder(root->right, ret); } public: vector<int> inorderTraversal(TreeNode* root) { vector<int> ret; InOrder(root,ret); return ret; } };
C语言版本
- 一样，给出C语言的代码求解，不做分析，你可理解前序后自己写写看
//中序遍历 void InOrder(struct TreeNode* root, int* a, int* pi) { if(!root) return; InOrder(root->left,a,pi); a[(*pi)++] = root->val; InOrder(root->right,a,pi); } //求二叉树大小 int TreeSize(struct TreeNode* root) { if(!root) return 0; return TreeSize(root->left) + TreeSize(root->right) + 1; } int* inorderTraversal(struct TreeNode* root, int* returnSize){ int i = 0; //1.首先获取二叉树大小 *returnSize = TreeSize(root); //2.动态开辟存放中序遍历的数组 int* a = (int *)malloc(sizeof(int) * (*returnSize)); //3.中序遍历 InOrder(root,a,&i); return a; }
- 下面是运行结果
【LeetCode】145.二叉树的后序遍历
题目描述.
思路分析.
- 后序也是一样的套路。在遍历完左右子树后再将根节点加入数组
代码详解.
C++版本
class Solution { private: void PostOrder(TreeNode* root, vector<int>& ret) { if(root == NULL) return; PostOrder(root->left, ret); PostOrder(root->right, ret); ret.push_back(root->val); } public: vector<int> postorderTraversal(TreeNode* root) { vector<int> ret; PostOrder(root,ret); return ret; } };
C语言版本
- 下面是C语言的代码
//后序遍历 void PostOrder(struct TreeNode* root, int* a, int* pi) { if(!root) return; PostOrder(root->left,a,pi); PostOrder(root->right,a,pi); a[(*pi)++] = root->val; } //求二叉树大小 int TreeSize(struct TreeNode* root) { if(!root) return 0; return TreeSize(root->left) + TreeSize(root->right) + 1; } int* postorderTraversal(struct TreeNode* root, int* returnSize){ int i = 0; //1.首先获取二叉树大小 *returnSize = TreeSize(root); //2.动态开辟存放中序遍历的数组 int* a = (int *)malloc(sizeof(int) * (*returnSize)); //3.中序遍历 PostOrder(root,a,&i); return a; }
- 下面是运行结果
