对称二叉树【leetcode - 101 - 简单】

末蓝、 2022-03-30 17:45 194阅读 0赞

胡扯：这个题，感觉挺好的。 这里给出两种思路，第二种思路是参考别人的思路写出来的，但是，里面的递归让我弄了很久，也让我对递归更加清楚了一些。事情慢慢变得有趣了 ...

## 思路一： ##

1、这个是我最先开始想到的思路代码也还好。

2、除去根节点，左右开始遍历。

3、左边按照  左根右 的顺序来遍历，右边按照 右根左 的顺序来遍历。叶子节点没有节点。其它节点如果只有一个子节点，另外一个用 \* 来代替，如果不这样会有问题，可以思考一下。

4、这样存储起来的两个字符串，对比如果相等。那么就是对称二叉树了。

代码一：

class Solution {
        
        
        String left = "";
        String right = "";
        void leftDfs(TreeNode root){
    
            if (root == null)
                return;
            left += root.val + "";
            if(root.left != null)
                leftDfs(root.left);
            else if(root.right != null)
                left += "*";
            if(root.right != null)
                leftDfs(root.right);
            else if(root.left != null)
                left += "*";
        }
        void RightDfs(TreeNode root){
    
            if (root == null)
                return;
            right += root.val + "";
            if(root.right != null)
                RightDfs(root.right);
            else if(root.left != null)
                right += "*";
            if(root.left != null)
                RightDfs(root.left);
            else if(root.right != null)
                right += "*";
        }
    
        public boolean isSymmetric(TreeNode root) {
    
            if (root == null ||  (root.right == null && root.left == null) )
                return true;
    
            leftDfs(root.left);
            RightDfs(root.right);
    
    //        System.out.println(left);
    //        System.out.println(right);
            return left.equals(right);
        }
    }

## 思路二： ##

1、这个思路是我提交成功后，看评论得出的思路。  【同时比较节点】

2、节点的遍历顺序也是， 左边   左根右， 右边  右根左。

3、如果相对位置不相同，那么就不是对称了。

4、这里困扰我最大的一个问题就是，除了相同位置 值，不一样不是对称，还有一种情况就是高低不一样的问题。其实这个如果想明白了就是很简单，没想明白就比较难了。

5、代码也比较简单，建议可以先按照这个思路写一遍。

代码二：

class Solution {
        
        boolean flag = true;
        void dfs(TreeNode l,TreeNode r){
    
            if (l.val != r.val){
                flag = false;
                return;
            }
            if (  l.left == null && l.right == null && r.left == null && r.right == null )
                return;
            if (l.left != null && r.right != null)
                dfs(l.left,r.right);
            else if (l.left != null || r.right != null)
                flag = false;
            if (l.right != null && r.left != null)
                dfs(l.right,r.left);
            else if (l.right != null || r.left != null)
                flag = false;
    
        }
        public boolean isSymmetric(TreeNode root) {
    
            if (root == null)
                return true;
            dfs(root,root);
            return flag;
        }
    }