特产网站开发的目的,商丘网站推广渠道,河北网站备案多久,上海市建设工程备案查询网站1.对称二叉树 题目链接#xff1a;101. 对称二叉树 - 力扣#xff08;LeetCode#xff09; 题解#xff1a; 我们可以用递归的方法去做#xff1a; 如果两个树互为镜像#xff08;1.根节点的值相同#xff0c;2.左子树的值与右子树的值对称#xff09;则为对称二叉树101. 对称二叉树 - 力扣LeetCode 题解 我们可以用递归的方法去做 如果两个树互为镜像1.根节点的值相同2.左子树的值与右子树的值对称则为对称二叉树我们先判断左右两棵树根节点的值如果根节点的值相同然后判断左右两棵树是否对称左边树的左孩子是否等于右边树的右孩子左边树的右孩子是否等于右边树的左孩子我们依次递归如果左右子树每个节点都满足以上两个条件则为对称二叉树。 注意需要对空进行判断如果两边对称位置都出现空则不影响结果如果两边对称位置一边为空另一边非空则不为对称二叉树 代码 bool is(struct TreeNode* root1,struct TreeNode* root2)
{if(root1NULLroot2NULL)return true;if(root1NULL||root2NULL)return false;if(root1-val ! root2-val)return false;return is(root1-left,root2- right)is(root1-right,root2-left);
}
bool isSymmetric(struct TreeNode* root) {return is(root-left,root-right);
} 2.翻转二叉树 题目链接226. 翻转二叉树 - 力扣LeetCode 题解 这一题其实就是上一题的变形我们可以看到翻转之后的图像和原来的图像是对称的关系因此我们只需要和上一题一样使用递归的操作依次对每个节点进行操作我们需要让左右两颗子树的对称位置节点的值进行交换这样就能变成原图像的对称图像。 代码 void _invertTree(struct TreeNode* root){if(root){struct TreeNode* tmp root-left;root-left root-right;root-right tmp;_invertTree(root-left);_invertTree(root-right);}
}struct TreeNode* invertTree(struct TreeNode* root){_invertTree(root);return root;
} 3.平衡二叉树 题目链接110. 平衡二叉树 - 力扣LeetCode 题解 首先要保证当前树的左右子树高度差不大于1而且子树本身也是平衡树。 这一题依然可以用递归的方法分别检查左右子树判断左右子树是否为平衡树然后检查总体的。因此我们要分别求出左右子树的高度判断两颗子树的高度差是否小于1这里可以用到绝对值左右子树都要进行这样的判断因此递归条件可以写为 fabs(TreeHeight(root-left)-TreeHeight(root-right))1isBalanced(root-left)isBalanced(root-right) 代码 int TreeHeight(struct TreeNode* root)
{if (root NULL)return 0;return fmax(TreeHeight(root-left), TreeHeight(root-right)) 1;
}
bool isBalanced(struct TreeNode* root) {if(rootNULL)return true;return fabs(TreeHeight(root-left)-TreeHeight(root-right))1isBalanced(root-left)isBalanced(root-right);
} 4.二叉树的前序遍历 题目链接144. 二叉树的前序遍历 - 力扣LeetCode 题解 要返回二叉树的前序遍历那么我们使用二叉树前序遍历访问一个节点就可以使用数组保存一个节点的值我们通过题目接口可以看到还要返回size所有我们还要求二叉树节点的size。 是 代码 void pre(struct TreeNode*root,int*a,int*i)
{if(rootNULL)return;a[(*i)]root-val;pre(root-left,a,i);pre(root-right,a,i);
}
int size(struct TreeNode*root)
{if(rootNULL){return 0;}return size(root-left)size(root-right)1;
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {int n size(root);*returnSize n;int*a(int*)realloc(a,sizeof(int)*n);int i0;pre(root,a,i);return a;
}
