【牛客 - 剑指offer】JZ28 对称的二叉树 两种方案 Java实现

---

剑指offer题解汇总 Java实现

https://blog.csdn.net/guliguliguliguli/article/details/126089434

本题链接

知识分类篇 - 树 - JZ28 对称的二叉树

题目

题目的主要信息是：判断一棵二叉树是否是镜像，即判断二叉树是否是轴对称图形

方案一 stack（我的解决思路）

用两个栈来存储节点

• stack1是从左边开始存储

• stack2是从右边开始存储

首先，在stack1和stack2中都存入根节点

进入循环，stack1，stack2，都弹出栈顶元素，比较弹出的栈顶元素的值

• 如果相等，则可以继续比较其左子节点和右子节点的情况

  • 由于第一次两个栈的栈顶元素都是在进入循环之前，加进去的根节点，所以，弹出的两个节点的值肯定是相同的

• 如果不等，则该棵二叉树不是对称的二叉树，return false

比较stack1当前节点的左子节点和stack2当前节点的右子节点

• 返回false的两种情况

  • 如果stack1当前节点的左子节点为空，stack2的当前节点的右子节点不为空，或者，stack1当前节点的左子节点不为空，stack2的当前右子节点为空，那么该棵二叉树不是对称的二叉树

  • 如果stack1当前节点的右子节点为空，stack2的当前节点的左子节点不为空，或者，stack1当前节点的右子节点不为空，stack2的当前左子节点为空，那么该棵二叉树不是对称的二叉树

• 添加新的节点到stack中的两种情况

  • 如果stack1的当前节点的左子节点和stack2的当前节点的右子节点都不为空，则向stack1中添加stack1当前节点的左子节点，向stack2中添加stack2当前节点的右子节点

  • 如果stack1的当前节点的右子节点和stack2的当前节点的左子节点都不为空，则向stack1中添加stack1当前节点的右子节点，向stack2中添加stack2当前节点的左子节点

• 不予考虑的情况

  • 如果stack1当前节点的左子节点和stack2当前节点的右子节点都为空，则不做任何处理

import java.util.*;

/*
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<>();

        s1.push(pRoot);
        s2.push(pRoot);

        while (!s1.isEmpty() && !s2.isEmpty()) {
            TreeNode n1 = s1.pop();
            TreeNode n2 = s2.pop();

            if (n1.val != n2.val) {
                return false;
            }

            if (n1.left != null && n2.right != null) {
                s1.push(n1.left);
                s2.push(n2.right);
            }

            if (n1.right != null && n2.left != null) {
                s1.push(n1.right);
                s2.push(n2.left);
            }

            if ((n1.left != null && n2.right == null) || (n1.left == null && n2.right != null)) {
                return false;
            }

            if ((n1.right != null && n2.left == null) || (n1.right == null && n2.left != null)) {
                return false;
            }
        }
        return true;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

稍加修改，思路一致

import java.util.*;

/*
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<>();

        s1.push(pRoot);
        s2.push(pRoot);

        while (!s1.isEmpty() && !s2.isEmpty()) {
            TreeNode n1 = s1.pop();
            TreeNode n2 = s2.pop();

            if (n1 == null && n2 == null) {
                continue;
            }

            if (n1 == null || n2 == null || n1.val != n2.val) {
                return false;
            }

            s1.push(n1.left);
            s1.push(n1.right);

            s2.push(n2.right);
            s2.push(n2.left);

        }
        return true;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

方案二 递归（推荐使用）

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能将原本的问题分解为更小的子问题，这是使用递归的关键。

而二叉树的递归，则是将某个节点的左子树、右子树看成一棵完整的树，那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题，因此可以自我调用函数，不断进入子树。

前序遍历的时候，采用的是“根左右”的遍历次序，如果这棵二叉树是对称的，即相应的左右节点交换位置完全没问题，那就可以尝试“根右左”遍历，按照轴对称图像的性质，这两种次序的遍历结果应该是一样的

注意
轴对称图像“根左右”，“根右左”的遍历顺序是一样的
但是，“根左右”，“根右左”的遍历顺序一样，不代表就是轴对称图形
例如
下面这幅图的“根左右”顺序是1 2 3 2 3，“根右左”顺序也是1 2 3 2 3

不同的方式遍历两次，将结果拿出来比较是一种可行的方法，但是，这种方式比较麻烦。

那么，可以直接在遍历的过程中比较。遍历的方式使用前序遍历的递归形式：

• 终止条件：当进入子问题的两个节点都为空，说明到了叶子节点，且是同步的，因此结束本次子问题，返回true；当进入子问题的两个节点只有一个为空，或者元素值不相等，说明这里的对称不匹配，同样结束本次子问题，返回false

• 返回值：每一级将子问题是否匹配的结果往上传递

• 本级任务：每个子问题，按照上述思路。“根左右”走左边的时候“根右左”走右边，“根左右”走右边的时候“根右左”走左边，一起进入子问题，需要两边都是匹配才能对称

import java.util.*;

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

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

    }

}
*/
public class Solution {
    boolean recursion(TreeNode root1, TreeNode root2) {
        //可以两个都为空
        if (root1 == null && root2 == null)
            return true;
        //只有一个为空或者节点值不同，必定不对称
        if (root1 == null || root2 == null || root1.val != root2.val)
            return false;
        //每层对应的节点进入递归比较
        return recursion(root1.left, root2.right) && recursion(root1.right, root2.left);
    }

    boolean isSymmetrical(TreeNode pRoot) {
        return recursion(pRoot, pRoot);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32