每日算法题【二叉树】：对称二叉树、二叉树的前中后序遍历

(3)对称二叉树

• 101. 对称二叉树 - 力扣（LeetCode）

• 解题思路：

  1. 算法思路：
     • 空树是对称的
     • 非空树需要满足：
       1. 左右子树的根节点值相等
       2. 左子树的左子树与右子树的右子树镜像对称
       3. 左子树的右子树与右子树的左子树镜像对称

  /*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*///自定义镜像比较函数，递归检查两个子树是否轴对称
  bool IsMirror(struct TreeNode* left,struct TreeNode* right){//左右子树均为空也证明子树对称if(left == NULL && right == NULL){//第一个递归结束条件return true;}//如果只有其中一个为空，证明不对称if(left == NULL || right == NULL){//第二个递归结束条件return false;}//俩子树根节点不同则不对称if(left->val != right->val){//第三个递归结束条件return false;}//如果两棵子树根节点相同则递下去看下一层的对称情况return IsMirror(left->left,right->right) && IsMirror(left->right,right->left);
  }bool isSymmetric(struct TreeNode* root) {//根节点为空默认轴对称if(root == NULL){return true;}//要比较两棵子树的对称情况，必须传入两个子树的根节点return IsMirror(root->left,root->right);
  }
  

(4)二叉树的前序遍历

• 144. 二叉树的前序遍历 - 力扣（LeetCode）

• 解题思路：

  利用递归的思想，前序遍历就是先遍历根节点，再遍历左子树，最后是右子树

  第一步：计算二叉树的节点总数并申请对应的数组空间

  第二步：通过前序遍历，将节点依次放入数组中，需注意索引要传地址，这样递归下去才会是同一个索引

  递归思想：首先找到递归条件（根节点为空则直接返回），因为是前序所以先对根节点进行操作，然后通过再次调用函数递到下一层子树的根节点，等最后一层的子树的根节点也为空，再依次返回。

  /*** 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 CountNodes(struct TreeNode* root,int* count){//通过前序遍历给传地址的count++//递归结束条件if(root == NULL){return;}(*count)++;             	//根节点CountNodes(root->left,count); //左子树CountNodes(root->right,count);//右子树
  }//前序遍历二叉树函数
  void PrevOrder(struct TreeNode* root,int* result,int* index){//递归结束条件if(root == NULL){return;}result[(*index)++] = root->val;     //根节点PrevOrder(root->left,result,index);//左子树PrevOrder(root->right,result,index);//右子树
  }int* preorderTraversal(struct TreeNode* root, int* returnSize) {//先计算节点总数来为创建的数组申请空间int count = 0;CountNodes(root,&count);//计算出来的节点数返还给returnSize并判空*returnSize = count;if(*returnSize == 0){return NULL;}//不为空则为数组申请空间int* result = (int*)malloc(count*sizeof(int));//通过自定义函数递归来填充数组int index = 0;PrevOrder(root,result,&index);return result;
  }
  

(5)二叉树中序遍历

• 94. 二叉树的中序遍历 - 力扣（LeetCode）

• 解题思路：

  同前序遍历一样

  /*** 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 CountNodes(struct TreeNode* root,int* count){//通过中序遍历给传地址的count++//递归结束条件if(root == NULL){return;}CountNodes(root->left,count); //左子树(*count)++;             	//根节点CountNodes(root->right,count);//右子树
  }//中序遍历二叉树函数
  void InOrder(struct TreeNode* root,int* result,int* index){//递归结束条件if(root == NULL){return;}InOrder(root->left,result,index);//左子树result[(*index)++] = root->val;     //根节点InOrder(root->right,result,index);//右子树
  }int* inorderTraversal(struct TreeNode* root, int* returnSize) {//先计算节点总数来为创建的数组申请空间int count = 0;CountNodes(root,&count);//计算出来的节点数返还给returnSize并判空*returnSize = count;if(*returnSize == 0){return NULL;}//不为空则为数组申请空间int* result = (int*)malloc(count*sizeof(int));//通过自定义函数递归来填充数组int index = 0;InOrder(root,result,&index);return result;
  }
  

(6)二叉树的后序遍历

• 145. 二叉树的后序遍历 - 力扣（LeetCode）

• 解题思路：

  同前序遍历一样

  /*** 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 CountNodes(struct TreeNode* root,int* count){//通过后序遍历给传地址的count++//递归结束条件if(root == NULL){return;}CountNodes(root->left,count); //左子树CountNodes(root->right,count);//右子树(*count)++;             	//根节点
  }//后序遍历二叉树函数
  void PostOrder(struct TreeNode* root,int* result,int* index){//递归结束条件if(root == NULL){return;}PostOrder(root->left,result,index);//左子树PostOrder(root->right,result,index);//右子树result[(*index)++] = root->val;     //根节点
  }int* postorderTraversal(struct TreeNode* root, int* returnSize) {//先计算节点总数来为创建的数组申请空间int count = 0;CountNodes(root,&count);//计算出来的节点数返还给returnSize并判空*returnSize = count;if(*returnSize == 0){return NULL;}//不为空则为数组申请空间int* result = (int*)malloc(count*sizeof(int));//通过自定义函数递归来填充数组int index = 0;PostOrder(root,result,&index);return result;
  }