Given a binary tree, return the inorder traversal of its nodes' values.
Example:
Input: [1,null,2,3]
1
\
2
/
3
Output: [1,3,2]
Output:
Follow up: Recursive solution is trivial, could you do it iteratively?
通过这道leetcode中的题目我们将学习，二叉树（中序 后序 前序）遍历递归与非递归实现，算法采用C编写，在非递归算法中如果采用C++中的栈来实现，将会非常简单。
递归实现
首先递归版本相对简单，先保存叶子节点值到result种，然后一层层往上，存在的多次申请与释放内存，效率较低。代码如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
int* inorderTraversal(struct TreeNode* root, int* returnSize)
{
int *result = NULL;
if (NULL == root)
return NULL;
int *leftarr=NULL, *rightarr=NULL, leftsize=0, rightsize=0;
int i = 0,j=0;
if(root->left)
leftarr = inorderTraversal(root->left,&leftsize);
if(root->right)
rightarr = inorderTraversal(root->right,&rightsize);
*returnSize = leftsize + 1 + rightsize;
result = (int *)malloc((*returnSize) * sizeof(int));
/*拷贝letfarr与rightarr指向的内容到result中*/
for(;i<leftsize;i++)
result[i] = leftarr[i];
/*存放根节点*/
result[i++] = root->val;
/*存放右子树*/
for(;j<rightsize;j++)
result[i + j] = rightarr[j];
/*释放内存*/
free(leftarr);
free(rightarr);
return result;
}
非递归实现
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
int* inorderTraversal(struct TreeNode* root, int* returnSize)
{
int *result = NULL;
*returnSize = 0;
struct TreeNode **stack = (struct TreeNode **)malloc(sizeof(struct TreeNode *));
int cur = 0;
while (cur >0 || root != NULL)
{
if (root)
{
stack = (struct TreeNode **)realloc(stack, sizeof(struct TreeNode *)*cur+1);
stack[cur++] = root;
root = root->left;
}
else
{
root = stack[--cur];
result = (int *)realloc(result, sizeof(int)*(*returnSize+1));
result[*returnSize] = root->val;
*returnSize += 1;
root = root->right;
}
}
return result;
}
算法实现思路：
1.针对当前节点，若其非空，将其入栈，并将其左孩子置为当前节点进行处理。
2.若其左孩子为空，则取栈顶元素并出栈，然后将该元素右孩子当做当前节点
3.直到栈空
附上man手册中对于函数realloc函数的说明：
The realloc() function changes the size of the memory block pointed to by ptr to size bytes. The contents will be unchanged in the range from the start of the region up to the minimum of the old and new sizes. If the new size is larger than the old size, the added memory will not be initialized. If ptr is NULL, then the call is equivalent to malloc(size), for all values of size; if size is equal to zero, and ptr is not NULL, then the call is equivalent to free(ptr). Unless ptr is NULL, it must have been returned by an earlier call to malloc(), calloc() or realloc(). If the area pointed to was moved, a free(ptr) is done.
2021.08.29更新
递归实现：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
visit(root,res);
return res;
}
private:
void visit(TreeNode* root,vector<int> &res) {
if(!root) return;
visit(root->left,res);
res.push_back(root->val);
visit(root->right,res);
}
};迭代实现：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> res;
while(root || !st.empty())
{
while(root)
{
res.push_back(root->val);
st.push(root);
root = root->left;
}
root = st.top();
st.pop();
root = root->right;
}
return res;
}
};
二叉树 前序 中序 后序遍历都可以使用上面迭代法的套路，后续遍历相对难实现一点，主要是因为需要一个prev指针，标记结点是否已完成遍历。
后序遍历迭代实现：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> st;
TreeNode* prev = nullptr;
while(root || !st.empty())
{
while(root)
{
st.push(root);
root = root->left;
}
root = st.top();
st.pop();
if(root->right == nullptr || root->right == prev)
{
res.push_back(root->val);
prev = root;
root = nullptr;
}else{
st.push(root);
root = root->right;
}
}
return res;
}
};