【LeetCode】3.19 对称二叉树

101. 对称二叉树

给你一个二叉树的根节点 root ，检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]

输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]

输出：false

提示：

树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100

进阶：你可以运用递归和迭代两种方法解决这个问题吗？

我的方法：老实巴交的层序遍历

使用修改的层序遍历（为空时也添加null），根据队列上次添加的元素个数获得每一层的节点数（包含空节点），然后再判断每一层的节点是否对称（暴击循环或者根据kmp的next数组判断最大公共前后缀），emmm总之就是做得特别麻烦。

递归做法

使用两个遍历同时循环判断，之前看题解做过一次，但是这次还是完全想不到，然后看了一眼想法直接写出来了，还需要多做啊

    public boolean isSymmetric(TreeNode root1, TreeNode root2) {

        if(root1 == null && root2 == null) {

            return true;

        } else if(root1 == null || root2 == null || root1.val != root2.val) {

            return false;

        } else {

            return isSymmetric(root1.left, root2.right)

                    && isSymmetric(root1.right, root2.left);

        }

    }

    public boolean isSymmetric(TreeNode root) {

        if(root == null) {

            return true;

        }

        return isSymmetric(root.left, root.right);

    }

非递归写法，类似层序遍历的写法

再次献上我的膝盖，直接看代码可能不是太理解，自己画一下图模拟下队列的过程就会立刻明白了

public boolean isSymmetric(TreeNode root) {

    if(root == null) {

        return true;

    }

    Queue<TreeNode> queue = new LinkedList<>();

    queue.add(root.left);

    queue.add(root.right);

    while(!queue.isEmpty()) {

        TreeNode leftNode = queue.poll();

        TreeNode rightNode = queue.poll();

        if(leftNode == null && rightNode == null) {

            continue;

        }

        if(leftNode == null || rightNode == null || leftNode.val != rightNode.val) {

            return false;

        }

        queue.add(leftNode.left);

        queue.add(rightNode.right);

        queue.add(leftNode.right);

        queue.add(rightNode.left);

    }

    return true;

}

巴特西

【LeetCode】3.19 对称二叉树

101. 对称二叉树

我的方法：老实巴交的层序遍历

递归做法

非递归写法，类似层序遍历的写法

最新文章

热门文章