首页 > 试题广场 >

对称的二叉树

[编程题]对称的二叉树
  • 热度指数:478586 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一棵二叉树,判断其是否是自身的镜像(即:是否对称)
例如:                                 下面这棵二叉树是对称的

下面这棵二叉树不对称。

数据范围:节点数满足 ,节点上的值满足
要求:空间复杂度 ,时间复杂度
备注:
你可以用递归和迭代两种方法解决这个问题
示例1

输入

{1,2,2,3,4,4,3}

输出

true
示例2

输入

{8,6,9,5,7,7,5}

输出

false

说明:本题目包含复杂数据结构TreeNode,点此查看相关信息
推荐
Ron头像 Ron
/*思路:首先根节点以及其左右子树,左子树的左子树和右子树的右子树相同
* 左子树的右子树和右子树的左子树相同即可,采用递归
* 非递归也可,采用栈或队列存取各级子树根节点
*/
public class Solution {
	boolean isSymmetrical(TreeNode pRoot)
	{
		if(pRoot == null){
			return true;
		}
		return comRoot(pRoot.left, pRoot.right);
	}
	private boolean comRoot(TreeNode left, TreeNode right) {
		// TODO Auto-generated method stub
		if(left == null) return right==null;
		if(right == null) return false;
		if(left.val != right.val) return false;
		return comRoot(left.right, right.left) && comRoot(left.left, right.right);
	}
}

编辑于 2015-08-18 23:10:28 回复(46)
class Solution
{
    bool isSymmetrical(TreeNode *p_root1, TreeNode *p_root2)
    {
        if (p_root1 == nullptr && p_root2 == nullptr)   // 对称的两个节点为空
            return true;
        else if (p_root1 == nullptr || p_root2 == nullptr)  // 其中一个节点不为空
            return false;
        if (p_root1->val != p_root2->val)   // 对称位置的值不相等
            return false;
        
        // 递归检查对称的位置:p1的左孩子和p2的右孩子,p1的右孩子p2的左孩子
        return isSymmetrical(p_root1->left, p_root2->right) && isSymmetrical(p_root1->right, p_root2->left);
    }
public:
    bool isSymmetrical(TreeNode *pRoot)
    {
        return isSymmetrical(pRoot, pRoot);
    }
};

发表于 2017-08-20 22:38:43 回复(0)
public class Solution {
    boolean a=true;
    boolean isSymmetrical(TreeNode pRoot)
    {
      if(pRoot==null)return a;
      cal(pRoot.left,pRoot.right);   
      return a;
    }
    void cal(TreeNode b,TreeNode c){
        if(b==null&&c==null){return;}
        if(b!=null&&c==null||b==null&&c!=null){a=false;return;}
        cal(b.left,c.right);
        if(b.val!=c.val){a=false;return;}
        cal(b.right,c.left);
        return;
    }
}
对称树的话除了跟节点随以外只需将其左右子树镜像对称,进行反方向遍历,如若有不等就返回false即可。
发表于 2016-07-15 15:57:57 回复(0)
class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot)
    {
    	if(pRoot == NULL) return true;
		return helper(pRoot->left,pRoot->right);
    }
    
    bool helper(TreeNode* l ,TreeNode* r){
        if(l == NULL && r == NULL) return true;
        if(l == NULL || r == NULL) return false;
        return l->val == r->val && helper(l->left,r->right) && helper(l->right , r->left);
    }
};

发表于 2015-08-20 12:34:43 回复(0)
class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot)
    {
        stack<TreeNode*> s1,s2;
        TreeNode *p1,*p2;
        p1=p2=pRoot;
        while((!s1.empty()&&!s2.empty())||(p1!=NULL&&p2!=NULL)){
            while(p1!=NULL&&p2!=NULL){
                s1.push(p1);
                s2.push(p2);
                p1=p1->left;
                p2=p2->right;
            }
            p1=s1.top();
            s1.pop();
         	p2=s2.top();
            s2.pop();
            if(p1->val!=p2->val)
                return false;
            p1=p1->right;
            p2=p2->left;
        }
    	if(!s1.empty()||!s2.empty())
            return false;
        if(p1!=NULL||p2!=NULL)
            return false;
        return true;
    }
};

发表于 2017-06-01 11:16:19 回复(1)
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    boolean isSymmetrical(TreeNode pRoot)
    {
        return frontOrBack(pRoot,pRoot);
    }
    
    public static boolean frontOrBack(TreeNode pRoot1,TreeNode pRoot2){
        if(pRoot1==null && pRoot2==null){
            return true;
        }
        if(pRoot1==null || pRoot2==null){
            return false;
        }
        
        if(pRoot1.val!=pRoot2.val){
            return false;
        }
        return frontOrBack(pRoot1.right,pRoot2.left) && frontOrBack(pRoot1.left,pRoot2.right);
    }
}

发表于 2018-05-30 10:57:31 回复(0)
boolean isSymmetrical(TreeNode pRoot) {
		if (pRoot == null)
			return true;
		return isSymmetrical(pRoot.left, pRoot.right);
	}
	//比较左右子树对应节点是否相同
	private boolean isSymmetrical(TreeNode pRoot1, TreeNode pRoot2) {
		if (pRoot1 == null && pRoot2 == null)
			return true;
		if (pRoot1 == null || pRoot2 == null)
			return false;
		if (pRoot1.val != pRoot2.val)
			return false;

		return isSymmetrical(pRoot1.left, pRoot2.right) && isSymmetrical(pRoot1.right, pRoot2.left);
	}

发表于 2017-06-09 11:21:16 回复(0)
class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot)
    {  
        if(pRoot == NULL) return true;  
    	return helper(pRoot->left, pRoot->right);                
    }
private:
    bool helper(TreeNode* node1, TreeNode* node2){
        if(node1==NULL && node2==NULL) 
            return true;
        else if(node1!=NULL && node2!=NULL)
        	return (node1->val==node2->val) && helper(node1->left, node2->right)
            	&& helper(node1->right, node2->left);
        else return false;
    }
};

发表于 2017-06-04 15:46:41 回复(0)
class isSymmetricalTree
{
public:
    bool isSymmetricalCore(TreeNode* pRoot,TreeNode* spRoot) //递归方法判断左右节点是否满足对称性
    {
        if(pRoot==nullptr && spRoot==nullptr) return true;
        if(pRoot!=nullptr && spRoot!=nullptr && pRoot->val==spRoot->val) //树节点值相等
            //递归,左右节点全满足对称性
            return isSymmetricalCore(pRoot->left,spRoot->right) && isSymmetricalCore(pRoot->right,spRoot->left);
        else
            return false;
    }
    bool isSymmetrical(TreeNode* pRoot)
    {
        if(pRoot==nullptr) return true;
        TreeNode* spRoot=pRoot;
        return isSymmetricalCore(pRoot,spRoot);
    }
};

发表于 2017-05-25 09:49:00 回复(0)
【java代码】满屏递归,无法挖掘这一题的价值。接下来提供递归的一个方法和非递归的2个方法参考。
//===================递归算法=============================//
1.只要pRoot.left和pRoot.right是否对称即可
2.左右节点的值相等对称子树left.left, right.right ;left.rigth,right.left也对称
 boolean isSymmetrical(TreeNode pRoot)
    {
        if(pRoot == null) return true;
        return isSymmetrical(pRoot.left, pRoot.right);
    }
    private boolean isSymmetrical(TreeNode left, TreeNode right) {
        if(left == null && right == null) return true;
        if(left == null || right == null) return false;
        return left.val == right.val //为镜像的条件:左右节点值相等
                && isSymmetrical(left.left, right.right) //2.对称的子树也是镜像
                && isSymmetrical(left.right, right.left);
    }
//===================非递归算法,利用DFS和BFS=============================//
/*
* DFS使用stack来保存成对的节点
* 1.出栈的时候也是成对成对的 ,
1.若都为空,继续;
2.一个为空,返回false;
3.不为空,比较当前值,值不等,返回false;
* 2.确定入栈顺序,每次入栈都是成对成对的,如left.left, right.right ;left.rigth,right.left
*/
 boolean isSymmetricalDFS(TreeNode pRoot)
    {
        if(pRoot == null) return true;
        Stack<TreeNode> s = new Stack<>();
        s.push(pRoot.left);
        s.push(pRoot.right);
        while(!s.empty()) {
            TreeNode right = s.pop();//成对取出
            TreeNode left = s.pop();
            if(left == null && right == null) continue;
            if(left == null || right == null) return false;
            if(left.val != right.val) return false;
            //成对插入
            s.push(left.left);
            s.push(right.right);
            s.push(left.right);
            s.push(right.left);
        }
        return true;
    }
/*
* BFS使用Queue来保存成对的节点,代码和上面极其相似
* 1.出队的时候也是成对成对
1.若都为空,继续;
2.一个为空,返回false;
3.不为空,比较当前值,值不等,返回false;
* 2.确定入队顺序,每次入队都是成对成对的,如left.left, right.right ;left.rigth,right.left
*/
 boolean isSymmetricalBFS(TreeNode pRoot)
    {
        if(pRoot == null) return true;
        Queue<TreeNode> s = new LinkedList<>();
        s.offer(pRoot.left);
        s.offer(pRoot.right);
        while(!s.isEmpty()) {
            TreeNode left= s.poll();//成对取出
            TreeNode right= s.poll();
            if(left == null && right == null) continue;
            if(left == null || right == null) return false;
            if(left.val != right.val) return false;
            //成对插入
            s.offer(left.left);
            s.offer(right.right);
            s.offer(left.right);
            s.offer(right.left);
        }
        return true;
    }

编辑于 2019-07-26 12:47:19 回复(65)
#Python 版
#思路: 同时进行中左右 和中右左的遍历,并在遍历的时候比较节点

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    def isSymmetrical(self, pRoot):
        if pRoot is None:
            return True
        return self.isSymmetricalCore(pRoot,pRoot)

    def isSymmetricalCore(self, pRoot, pRoot1):
        if pRoot is None and pRoot1 is None:
            return True
        if pRoot is None or pRoot1 is None:
            return False
        if pRoot.val != pRoot1.val :
            return False
        return self.isSymmetricalCore(pRoot.left,pRoot1.right) and self.isSymmetricalCore(pRoot.right,pRoot1.left)

发表于 2016-12-08 22:40:26 回复(0)
public class Solution {
    boolean isSymmetrical(TreeNode pRoot){
        if(pRoot==null)
            return true;
        return isMirror(pRoot.left,pRoot.right);

    }
    public boolean isMirror(TreeNode left,TreeNode right){
        if(left==null&&right==null)
            return true;
        if((left==null&&right!=null)
           ||(right==null&&left!=null)
           ||(left.val!=right.val)
           ||!(isMirror(left.left,right.right))
           ||!(isMirror(right.left,left.right))
          )
            return false;
        return true;
    }
}

发表于 2016-04-17 22:23:15 回复(0)
采用递归的思想:同时遍历左右子树

发表于 2015-05-22 09:07:00 回复(0)
public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {
        if(pRoot==null){
            return true;
        }
        return judge(pRoot,pRoot);
    }
    boolean judge(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) {
            return true;
        }
        if (root1 != null && root2 != null && root1.val == root2.val) {
            return judge(root1.left, root2.right) && judge(root1.right, root2.left);
        }
        return false;
    }
}
发表于 2022-05-27 13:18:49 回复(1)
递归判空判值完事
    boolean isSymmetrical(TreeNode pRoot) {
        if(pRoot==null)
            return true;
        return isSymmetrical(pRoot.left,pRoot.right);
    }
    
    boolean isSymmetrical(TreeNode p,TreeNode q) {
        if(p==null && q==null)
            return true;
        if(p==null || q==null)
            return false;
        if(p.val != q.val)
            return false;
        return isSymmetrical(p.left,q.right) && isSymmetrical(p.right,q.left);
    }
发表于 2022-03-12 15:27:02 回复(0)
方法1:拆成左右子树两个参数,用新函数递归
class Solution:
    '''法1:递归但不构造虚拟结点,改成多参数递归即可'''
    def isSym(self, p_left, p_right):
        if not p_left and not p_right: return True
        if not p_left&nbs***bsp;not p_right: return False
        if p_left.val != p_right.val: return False
        return self.isSym(p_left.left, p_right.right) and self.isSym(p_left.right, p_right.left)
    def isSymmetrical(self , pRoot: TreeNode) -> bool:
        return True if not pRoot else self.isSym(pRoot.left, pRoot.right)
方法2:构造对称轴虚拟结点,用原函数递归
class Solution:
    def isSymmetrical(self , pRoot: TreeNode) -> bool:
        '''法2:构造对称轴结点递归'''
        if not pRoot: return True
        if not pRoot.left and not pRoot.right: return True
        if not pRoot.left or not pRoot.right: return False
        if pRoot.left.val != pRoot.right.val: return False
        virtual_node_1, virtual_node_2 = TreeNode(0), TreeNode(0)
        virtual_node_1.left, virtual_node_1.right = pRoot.left.left, pRoot.right.right
        virtual_node_2.left, virtual_node_2.right = pRoot.left.right, pRoot.right.left
        return self.isSymmetrical(virtual_node_1) and self.isSymmetrical(virtual_node_2)
方法3:用队列
class Solution:
    def isSymmetrical(self , pRoot: TreeNode) -> bool:)
        '''法1:队列'''
        if not pRoot: return True
        if not pRoot.left and not pRoot.right: return True
        if not pRoot.left&nbs***bsp;not pRoot.right: return False
        queue_l, queue_r = [pRoot.left], [pRoot.right]
        while queue_l != [] and queue_r != []:
            if queue_l[0].val != queue_r[0].val: return False
            l_pop, r_pop = queue_l.pop(0), queue_r.pop(0)
            if l_pop.left:
                if not r_pop.right: return False
                queue_l.append(l_pop.left)
                queue_r.append(r_pop.right)
            if l_pop.right:
                if not r_pop.left:  return False
                queue_l.append(l_pop.right)
                queue_r.append(r_pop.left)
        return queue_l == [] and queue_r == []
发表于 2022-02-27 20:06:40 回复(0)
两个栈分别对两边进行判断,易于理解
import java.util.Stack;

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {
        if(pRoot == null) return true;
        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        TreeNode t1 = pRoot;
        TreeNode t2 = pRoot;
        while((t1!=null && t2 != null) ||(!s1.isEmpty() && !s2.isEmpty())){
            while(t1!=null){
                s1.push(t1);
                t1 = t1.left;
            }
            while(t2!=null){
                s2.push(t2);
                t2 = t2.right;
            }
            TreeNode temp1 = s1.pop();
            TreeNode temp2 = s2.pop();
            if(temp1.val!=temp2.val)
                return false;
            t1 = temp1.right;
            t2 = temp2.left;
        }
        if(!s1.isEmpty() || !s2.isEmpty()){
            return false;
        }
        return true;
    }
}

发表于 2022-01-06 10:11:00 回复(0)
public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {
        //    空树也是对称的
        if(pRoot == null)
            return true;
        
        return helper(pRoot.left, pRoot.right);
    }
    
    private boolean helper(TreeNode pRootL, TreeNode pRootR){
        //    一直对比到最下面一层,还没有返回说明是对称的二叉树
        if(pRootL == null && pRootR == null)
            return true;
        //    如果对比的过程中出现一边为空,另一边不为空的情况,说明不是对称的二叉树
        else if(pRootL == null || pRootR == null)
            return false;
        //    否则向下去对比:pRootL和pRootR所指向的数值必须相同,同时,
        //    pRootL和pRootR向下走的时候,需要往相反的方向走
        else return pRootL.val == pRootR.val &&
                helper(pRootL.left, pRootR.right) && helper(pRootL.right, pRootR.left);
    }
}

发表于 2021-11-14 10:25:04 回复(0)
我好像写代码总是这样,没有想到很好的办法,大多数情况都是穷举,而且有时候还过不了,需要爆出来的测试用例,一点一点的加上许多if。

你能想到还有这样的测试用例吗?


{5,5,5,5,#,#,5,5,#,5}
期望输出:false
    
{5,5,5,5,#,#,5,5,#,#,5}
期望输出:true


发表于 2021-09-16 17:06:35 回复(0)
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot) 
    {
        if(pRoot == nullptr)
            return true;
        else
            return isSymmetrical(pRoot -> left, pRoot -> right);
    }
    
    bool isSymmetrical(TreeNode* left, TreeNode* right)
    {
        if(left == nullptr && right == nullptr)
        {
            return true;
        }
        
        if(left == nullptr || right == nullptr || left -> val != right -> val)
        {
            return false;
        }
        
        return isSymmetrical(left -> left, right -> right) && isSymmetrical(left -> right, right -> left);
    }
};

发表于 2021-08-30 22:37:44 回复(0)
public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {
        if(pRoot == null) {
            return true;
        }
        return check(pRoot.left, pRoot.right);
    }
    
    public boolean check(TreeNode L, TreeNode R) {
        if(L == null && R == null) {
            return true;
        }
        if(L == null || R == null) {
            return false;
        }
        if(L.val != R.val) {
            return false;
        }
        return check(L.left, R.right) && check(L.right, R.left);
    }
}

发表于 2021-08-06 20:38:05 回复(0)