【Hot 100 刷题计划】 LeetCode 101. 对称二叉树 | C++ DFS 极简递归模板

LeetCode 101. 对称二叉树 题目描述题目级别简单给你一个二叉树的根节点root 检查它是否轴对称。示例 1:输入root [1,2,2,3,4,4,3]输出true示例 2:输入root [1,2,2,null,3,null,3]输出false 破题思路递归 (DFS 同步双指针)判断一棵树是否对称本质上是判断它的左子树和右子树是否互为镜像。这需要我们派出两个指针l和r分别去巡视左子树和右子树。巡视的规则必须像照镜子一样基本盘校验如果l和r都为空说明对称到了叶子节点的下面。如果l和r只有一个为空或者它们的值不相等说明不对称直接判死刑false。镜像前行核心魔法外侧对外侧左指针往左走的同时右指针必须往右走去比较l-left和r-right。内侧对内侧左指针往右走的同时右指针必须往左走去比较l-right和r-left。只有当外侧和内侧都对称时这棵树才是真正的对称树。 C 代码实现 (极简递归版)classSolution{public:boolisSymmetric(TreeNode*root){// 如果树为空天然对称否则开启双指针镜像递归return!root||dfs(root-left,root-right);}booldfs(TreeNode*l,TreeNode*r){// 1. 两人同时走到空节点说明一路过来都对称if(!l!r)returntrue;// 2. 只有一人为空或者两人的值不相等结构/数值被破坏不对称elseif(!l||!r||l-val!r-val)returnfalse;// 3. 镜像递归比较外侧节点 比较内侧节点returndfs(l-left,r-right)dfs(l-right,r-left);}};