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

​94.二叉树的中序遍

二叉树中序遍历的顺序：遍历左子树(直到最后一个左子树为空)-前一个根节点-遍历右子树。

递归实现中序遍历

94.二叉树的中序遍

该树的结构：

数的结构

遍历顺序：NULL->1->2->3->NULL

输出顺序：1->3->2

代码演示

/*struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};
*/
​
int TreeSize(struct TreeNode *root)     //因为要输出，需要知道树中值的个数
{
    if(!root)
        return 0;
    return TreeSize(root->left)+TreeSize(roo->right)+1;
}
void Traversal(struct TreeNode *root,int *returnSize,int *a) //returnsize记录输出的次序，a为记录数值的数组
{
    if(!root)
        return ;
    Traversal(root->left,returnSize,a);
    a[(*returnSize)++]=root->val;
    Traversal(root->right,returnSize,a);
}
int *inorderTraversal(struct TreeNode *root,int *returnSize)
{
    int treesize=TreeSize(root);
    int *a=(int *)malloc(treesize*sizeof(int)); 
    memset(a,0,treesize);   //将数组初试化为0
    *returnSize=0;
    Traversal(root,returnSize,a);
    return a;
}

代码依照参照Leetcode一位叫师太饶了老衲的用户。他还给出了除递归解法的栈解法。

代码分析

在这个递归解法中，有两个比较难以理解的问题，二叉树数的计算过程和二叉树遍历过程。这两个地方全都用了递归思想。

//return TreeSize(root->left)+TreeSize(root->right)+1

个数的计算过程

计算过程

遍历过程：1的左子树，为空->在输出数组中记录前一个根节点的值(1)->1的右子树(2)，不为空->2的左子树(3)，不为空->3的左子树,为空->记录前一个根节点的值(3)->3的右子树为空，返回到上一个根节点2,并记录->2的右子树，为空，结束。

遍历过程

递归思想最重要理解：递归的停止判断条件，对于递归过程理解，可以通过画图来帮助自己理解其运行过程。

复杂度分析

1.时间复杂度：O(n)。递归函数 T(n) = 2·T(n/2)+1。2.空间复杂度：最坏情况下需要空间O(n)，平均情况为O(log n)