day10_LC学习计划：数据结构入门_root = [1,null,2,3]

作者：odstu | 2024-01-31 12:56:27

踩

root = [1,null,2,3]

144.二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的前序遍历。

示例 1：

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

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

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

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

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

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、idea：

前中后序遍历真数据结构基操了，迭代和递归，不过还是有不会写的地方，果然光是看懂真不行。

二、解法：

略。

三、代码实现细节的学习：

在递归时，一开始不知道如何让保存结果的数组序号向后移动。
重新理解了一下C中的指针，当指针已经开辟了空间的时候，*p便可以像只有一位数字的p数组的p[0]处存放int类型的数据。
*p=&a，在没有开辟内存空间时候，指针指向地址才是正确的赋值方式。
C中的指针在传递的过程中也是传递的地址，所以在不同的函数中

1、递归，解答则避免了全局变量内存空间的开辟。


/**
 * 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().
 */
 
int *ret;
 
int i;
 
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    i=0;
    ret=malloc(sizeof(int)*100);
    preorder(root);
    *returnSize=i;
    return ret;
}
 
void preorder(struct TreeNode *root){
    if(root==NULL) return;
    ret[i++]=root->val;
    preorder(root->left);
    preorder(root->right);
}

2、在迭代时，题解中的思想里，栈中只保存上一个该向右结点遍历的结点。

while里的第一个node!=NULL是为了保证右子树和栈不都为空，第二个是为了保证左子树不为空。


/**
 * 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().
 */
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int *ret=malloc(sizeof(int)*100);
    *returnSize=0;
    if(root==NULL) return ret;
    struct TreeNode* stack[100];
    struct TreeNode* node=root;
    int top=-1;
    while(node!=NULL||top>-1){
        while(node!=NULL){
            ret[(*returnSize)++]=node->val;
            stack[++top]=node;
            node=node->left;
        }
        node=stack[top--];
        node=node->right;
    }
    return ret;
}

3、Morris算法，第一次接触到，常看常新，自己实现的时候错误的地方已经标注在代码上了。


/**
 * 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().
 */
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int *ret=malloc(sizeof(int)*100);
    *returnSize=0;
    if(root==NULL) return ret;
 
    struct TreeNode *p1=root,*p2=NULL;
    while(p1!=NULL){
        p2=p1->left;
        if(p2!=NULL){
            while(p2->right!=NULL&&p2->right!=p1){
                p2=p2->right;
            }
            if(p2->right==NULL){
                ret[(*returnSize)++]=p1->val;
                p2->right=p1;
                p1=p1->left;
                continue;//不加这个就直接向右走了
            }else{
                p2->right=NULL;//如果p2的右子树不为空，那就直接恢复原本的树就可以了
            }
        }else{
            ret[(*returnSize)++]=p1->val;//如果p2为空，说明左子树为空。
        }
        p1=p1->right;
    }
    return ret;
}

94.二叉树的中序遍历

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

示例 1：

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

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

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

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

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

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、idea：

略

二、解法：

略

三、代码实现细节的学习：

1、递归


/**
 * 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().
 */
int* inorderTraversal(struct TreeNode* root, int* returnSize){
    int *ret=malloc(sizeof(int)*100);
    *returnSize=0;
    inorder(root,ret,returnSize);
    return ret;
}
 
void inorder(struct TreeNode* root, int* ret, int* returnSize){
    if(root==NULL) return;
    inorder(root->left, ret, returnSize);
    ret[(*returnSize)++]=root->val;
    inorder(root->right, ret, returnSize);
}

2、迭代


/**
 * 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().
 */
int* inorderTraversal(struct TreeNode* root, int* returnSize){
    int *ret=malloc(sizeof(int)*100);
    *returnSize=0;
    if(root==NULL) return ret;
 
    struct TreeNode* stack[100];
    int top=-1;
    while(root!=NULL||top>-1){//应该保证栈不为空或者root不为空就行
        while(root!=NULL){
            stack[++top]=root;//在这里应该放入当前节点
            root=root->left;
        }
        root=stack[top--];//要先从栈中取出
        ret[(*returnSize)++]=root->val;
        root=root->right;
    }
    return ret;
}

3、Morris算法


/**
 * 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().
 */
int* inorderTraversal(struct TreeNode* root, int* returnSize){
    int *ret=malloc(sizeof(int)*100);
    *returnSize=0;
    struct TreeNode* node=root;
    while(node!=NULL){
        if(node->left!=NULL){
            struct TreeNode* tmp=node->left;//按算法这里应该是node->left!!
            while(tmp->right!=NULL&&tmp->right!=node){
                tmp=tmp->right;
            }
            if(tmp->right==NULL){
                tmp->right=node;
                node=node->left;//这里不用continue，因为这次的写法，指针向右写在了else里边
                //continue;
            }else{
                ret[(*returnSize)++]=node->val;
                tmp->right=NULL;//这个前驱的右子树只是一个标记作用，标记左子树是否完成遍历。
                node=node->right;
            }
        }else{
            ret[(*returnSize)++]=node->val;
            node=node->right;
        } 
        //node=node->right;不理解写在这为什么会有空指针异常
    }
    return ret;
}

145.二叉树的后序遍历

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

示例 1：

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

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

输入：root = [1]
输出：[1]

提示：

树中节点的数目在范围 [0, 100] 内
-100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、idea：

略

二、解法：

略

三、代码实现细节的学习：

1、递归


/**
 * 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().
 */
int* postorderTraversal(struct TreeNode* root, int* returnSize){
    int *ret=malloc(sizeof(int)*100);
    *returnSize=0;
    postorder(root,ret,returnSize);
    return ret;
}
 
void postorder(struct TreeNode* root, int* ret, int* returnSize){
    if(root==NULL) return;
    postorder(root->left,ret,returnSize);
    postorder(root->right,ret,returnSize);
    ret[(*returnSize)++]=root->val;
}

2、迭代，自己该注意的已经写了注释。


/**
 * 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().
 */
int* postorderTraversal(struct TreeNode* root, int* returnSize){
    int *ret=malloc(sizeof(int)*100);
    *returnSize=0;
    if(root==NULL) return ret;
 
    struct TreeNode* stack[100],*prev;
    int top=-1;
    while(root!=NULL||top>-1){
        while(root!=NULL){
            stack[++top]=root;
            root=root->left;
        }
        root=stack[top--];
        if(root->right==NULL||root->right==prev){
            ret[(*returnSize)++]=root->val;
            prev=root;
            root=NULL;//后序遍历用栈需要有一个置空指针操作，还需要判断被置空的是不是栈里
        }else{//弹出的下一个节点的右节点，如果是右节点，说明左右子节点都已经遍历了
            stack[++top]=root;//如果都不是，说明是根节点的左子节点，放回栈里继续等待遍历。
            root=root->right;
        }
    }
    return ret;
}

3、Morris算法，整个算法不能说算太懂，搭配上倒序算法更是不知道为什么可以这样，后续有时间再深究吧。


/**
 * 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().
 */
void addPath(int *ret, int *returnSize, struct TreeNode* node){
    int count=0;//简单的反转算法
    while(node!=NULL){//倒序算法，目前还没有弄懂原理。
        count++;
        ret[(*returnSize)++]=node->val;
        node=node->right;
    }
    for(int i=*returnSize-count,j=*returnSize-1;i<j;i++,j--){
        int tmp=ret[i];
        ret[i]=ret[j];
        ret[j]=tmp;
    }
}
 
int* postorderTraversal(struct TreeNode* root, int* returnSize){
    int *ret=malloc(sizeof(int)*100);//这个Morris算法的访问顺序是4，2，5，1，3，6中序序列
    *returnSize=0;
    if(root==NULL) return ret;
 
    struct TreeNode *p1=root,*p2=NULL;
    while(p1!=NULL){
        p2=p1->left;
        if(p2!=NULL){
            while(p2->right!=NULL&&p2->right!=p1){
                p2=p2->right;
            }
            if(p2->right==NULL){
                p2->right=p1;
                p1=p1->left;
                continue;
            }else{
                p2->right=NULL;
                addPath(ret,returnSize,p1->left);
            }
        }
        p1=p1->right;
    }
    addPath(ret,returnSize,root);
    return ret;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/article/detail/50412