【Leetcode -101.对称二叉树 -144.二叉树的前序遍历】

简介: 【Leetcode -101.对称二叉树 -144.二叉树的前序遍历】

Leetcode -101.对称二叉树

题目:给你一个二叉树的根节点 root , 检查它是否轴对称。

示例 1:

输入:root = [1, 2, 2, 3, 4, 4, 3]

输出:true

示例 2:

输入:root = [1, 2, 2, null, 3, null, 3]

输出:false

提示:

树中节点数目在范围[1, 1000] 内

  • 100 <= Node.val <= 100

思路:化为子问题比较左子树和右子树是否对称;结束条件为空或者值不相等;

bool isSameTree(struct TreeNode* leftRoot, struct TreeNode* rightRoot)
    {
        //都为空符合要求
        if (leftRoot == NULL && rightRoot == NULL)
            return true;
        //一个为空一个不为空,不符合
        if (leftRoot == NULL || rightRoot == NULL)
            return false;
        //值不相等不符合
        if (leftRoot->val != rightRoot->val)
            return false;
        //左根的左子树和右根的右子树比较;左根的右子树和右根的左子树比较
        return isSameTree(leftRoot->left, rightRoot->right) && isSameTree(leftRoot->right, rightRoot->left);
    }
    bool isSymmetric(struct TreeNode* root)
    {
        if (root == NULL)
            return true;
        //比较根的左子树和右子树
        return isSameTree(root->left, root->right);
    }

Leetcode -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

思路:先计算节点个数,开辟返回数组;化为子问题每个子树都先打印根,再左子树,最后右子树;结束条件为空;

//计算节点数
    int TreeSize(struct TreeNode* root)
    {
        if (root == NULL)
            return 0;
        return TreeSize(root->left) + TreeSize(root->right) + 1;
    }
    void PrevOrder(struct TreeNode* root, int* ans, int* pi)
    {
        //如果空返回
        if (root == NULL)
            return;
        //先存放根的val,再左子树,后右子树
        ans[(*pi)++] = root->val;
        PrevOrder(root->left, ans, pi);
        PrevOrder(root->right, ans, pi);
    }
    int* preorderTraversal(struct TreeNode* root, int* returnSize)
    {
        //先计算节点的个数
        *returnSize = TreeSize(root);
        int* ans = (int*)malloc(*returnSize * sizeof(int));
        int i = 0;
        //前序遍历
        PrevOrder(root, ans, &i);
        return ans;
    }
目录
相关文章
|
21天前
【LeetCode 31】104.二叉树的最大深度
【LeetCode 31】104.二叉树的最大深度
16 2
|
21天前
【LeetCode 29】226.反转二叉树
【LeetCode 29】226.反转二叉树
15 2
|
21天前
【LeetCode 28】102.二叉树的层序遍历
【LeetCode 28】102.二叉树的层序遍历
12 2
|
21天前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
11 0
|
21天前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
10 0
|
21天前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
10 0
|
21天前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
11 0
|
21天前
【LeetCode 32】111.二叉树的最小深度
【LeetCode 32】111.二叉树的最小深度
12 0
|
3月前
|
存储 算法
二叉树进阶-学会层序遍历助你一次刷完leetcode10道题
文章深入探讨了二叉树的层序遍历方法,并展示了如何通过队列实现层序遍历的算法逻辑,同时指出掌握层序遍历技巧可以帮助解决LeetCode上的多道相关题目。
二叉树进阶-学会层序遍历助你一次刷完leetcode10道题
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行