从零开始算法之路 ----对称二叉树

待我称王封你为后i 2022-01-12 09:01 194阅读 0赞

前言：小白入门题解，算法大佬可以直接跳过此博客（大佬轻喷哈）

题源：leetcode（[https://leetcode-cn.com/problems/symmetric-tree/）][https_leetcode-cn.com_problems_symmetric-tree]

题目描述：  
给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

**解决方案：递归**  
思路:  
  (1) 如果这棵树是空树,则返回true  
  (2) 如果树的左子树为空，右子树不为空，则返回 false  
  (3) 否则就递归去判断左子树的右子树和右子树的左子树是否相等如果相等，返回 true,若不相等 ，则返回false

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    class Solution { 
    public:
       bool  isSymmtric_second( TreeNode* left, TreeNode* right)
     { 
        
       	if(left == NULL && right == NULL)
    		return true;
        // (2) 如果树的左子树为空，右子树不为空，则返回 false
    	if(left == NULL || right == NULL)
    		return false;
        // (3) 否则就递归去判断左子树的右子树和右子树的左子树是否相等
    	// 如果相等，返回 true,若不相等 ，则返回false
    	return left->val == right->val
    	       && isSymmtric_second(left->left, right->right)
    	       && isSymmtric_second(left->right, right->left);
     }
     
    bool isSymmetric( TreeNode* root) {     
         // (1) 如果这棵树是空树,则返回true
    	if(root == NULL)
    		return true;
    	else
    		return isSymmtric_second(root->left, root->right);
    
    }
    };

[https_leetcode-cn.com_problems_symmetric-tree]: https://leetcode-cn.com/problems/symmetric-tree/%EF%BC%89