《剑指offer》刷题笔记。如有更好解法,欢迎留言。
关键字:树
深度优先遍历
题目描述:
请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。
思路:
- 简单暴力的方法就是生成镜像树,再比较。
- 这里直接递归遍历,比较左子树的左节点与右子树的右节点,还有左子树的右节点与右子树的左节点。
function isSymmetrical(pRoot)
{
if(!pRoot){
return true;
}
function dfs(left,right){
if(left === null && right === null){
return true;
}
if(left !== null && right !== null && left.val === right.val){
return dfs(left.left,right.right)&&dfs(left.right,right.left);
}
return false;
}
return dfs(pRoot.left,pRoot.right);
}