Two solutions: BFS iteration or recursion


  • 0
    F

    1、 BFS:
    Two trees which are symmetric have the same iterative result of BFS with two different direction. As we can see in code below: we search sub-tree of root.left with left ---> right sequence in each layer, and sub-tree of root.right with right ---> left sequnce, if two sub-tree are both mirrors of each other, the BFS result (store in a String ) should be same.

    public boolean isSymmetric(TreeNode root) {
            if(root==null)
                return true;
            String bfsLeft=bfs(root.left,0);
            String bfsRight=bfs(root.right,1);
            return bfsLeft.equals(bfsRight);
        
            
        }
        public String bfs(TreeNode root,int direction){
            StringBuilder sb=new StringBuilder();
            Queue<TreeNode> q=new LinkedList<TreeNode>();
            q.add(root);
            while(!q.isEmpty()){
                TreeNode t=q.poll();
                if(t==null){
                    sb.append(String.valueOf("#"));
                    continue;
                }
                sb.append(String.valueOf(t.val));
                TreeNode[] leftRight;
                if(direction==0){
                    leftRight=new TreeNode[]{t.left,t.right};
                }else{
                    leftRight=new TreeNode[]{t.right,t.left};
                }
                q.add(leftRight[0]);
                q.add(leftRight[1]);
            }
            return sb.toString();
        }
    

    2、recursion solution
    recursion solution is intuitionistic and similar with most solutions of others'.

    public boolean isSymmetric(TreeNode root){
        if(root==null)
            return true;
        return isTwoSymmetrix(root.left,root.right);
    }
    public boolean isTwoSymmetrix(TreeNode t1,TreeNode t2){
        if(t1==null && t2==null)
            return true;
        else if(t1!=null && t2!=null){
            if(t1.val!=t2.val)
                return false;
            if(!isTwoSymmetrix(t1.left,t2.right))
                return false;
            if(!isTwoSymmetrix(t1.right,t2.left))
                return false;
            return true;
        }
        return false;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.