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; }