C語言遞回之對稱二叉樹-有解無憂

題目描述

給定一個二叉樹，檢查它是否是鏡像對稱的，

示例

二叉樹 [1,2,2,3,4,4,3] 是對稱的，

[1,2,2,null,3,null,3] 則不是鏡像對稱的，

題目要求

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     struct TreeNode *left;
 6  *     struct TreeNode *right;
 7  * };
 8  */
 9 
10 bool isSymmetric(struct TreeNode* root){
11 
12 }

題解

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     struct TreeNode *left;
 6  *     struct TreeNode *right;
 7  * };
 8  */
 9 
10 bool fun(struct TreeNode* r1,struct TreeNode* r2){
11     if(r1==NULL&&r2==NULL)return true;
12     if(r1==NULL||r2==NULL)return false;
13     if(r1->val!=r2->val)return false;
14     return fun(r1->left,r2->right)&fun(r1->right,r2->left);
15 }
16 
17 bool isSymmetric(struct TreeNode* root){  
18     if(root==NULL)return true;
19     return fun(root->left,root->right);  
20 }

題解

遞回

遞回的難點就在于想出要遞回什么，經常情況是看了一下有那么點思路，但是一寫就不會，真正想明白之后恍然大悟，還是要耐心思考，

對于此題，判斷遞回點就需要一步一步分析：

1.判斷一棵樹是不是對稱二叉樹，首先看根節點，根節點為空則true，根節點不為空則比較其左樹和右樹，左樹右樹對稱時則為對稱二叉樹，

2.比較左樹右樹是否對稱，首先需要左樹的值和右樹的值相等，其次需要左樹的左子樹與右樹的右子樹相等且左樹的右子樹與右樹的左子樹相等，否則不對稱，

3.此時遞回點就出現了，判斷左樹與右樹是否對稱的操作其實和判斷左樹的左子樹與右樹的右子樹是否對稱的操作相同，

4.這時就可以直接寫代碼了，fun(左樹, 右樹) = fun(左樹的左子樹, 右樹的右子樹) & fun(左樹的右子樹, 右樹的左子樹)，

題目來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/symmetric-tree/
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/139965.html

標籤：其他

上一篇：演算法題--最長回文子串

下一篇：C語言遞回之翻轉二叉樹