对称二叉树（递归+迭代）

た入场券 2023-02-23 12:10 42阅读 0赞

### 题目 ###

给定一个二叉树，检查它是否是镜像对称的。

**例如，二叉树 \[1,2,2,3,4,4,3\] 是对称的。**

1
       / \
      2   2
     / \ / \
    3  4 4  3

**但是下面这个 \[1,2,2,null,3,null,3\] 则不是镜像对称的:**

1
       / \
      2   2
       \   \
       3    3

### **题目思路** ###

对于这道题，要求判断一颗二叉树是否是对称的。

这里所说的对称，就是轴对称。因此在判断上，可以直接使用递归的思路，也可也使用非递归的方法，

### 递归 ###

**写一个递归函数，当且仅当两个节点的值相等且节点的孩子也对称的时候返回true。**

/**
     * 请实现一个函数，用来判断一颗二叉树是不是对称的 递归方式实现
     * 写一个递归函数，当且仅当两个节点的值相等且节点的孩子也对称的时候返回true。
     * @author: MrBlackWhite
     * @data: 2020-07-07 11:45
     **/
    public class BinaryTreeRecurrence {
        /**
         * 是否为对称树
         */
        public boolean isSymmetric(TreeNode root) {
            if (root == null) {
                return true;
            }
            return recurrenceHelper(root.left, root.right);
        }
    
        public boolean recurrenceHelper(TreeNode root1, TreeNode root2) {
            if ((root1 == null && root2 != null) || (root1 != null && root2 == null)) {
                return false;
            } else if (root1 != null && root2 != null) {
                return root1.val == root2.val
                        && recurrenceHelper(root1.left, root2.right)
                        && recurrenceHelper(root1.right, root2.left);
            }
            return true;
        }
    }

### 迭代 ###

/**
     * 请实现一个函数，用来判断一颗二叉树是不是对称的 迭代实现
     * 迭代的思路就是层次遍历，最开始将根节点入队两次，然后每次出队两个节点A和B，比较两个节点。
     * 若不同时为空或者值不相等，说明不是镜像；
     * 若相等，将节点A的左孩子与节点B的右孩子一起入队，将节点A的右孩子与节点B的左孩子一起入队。
     *
     * @author: MrBlackWhite
     * @data: 2020-07-07 11:45
     **/
    public class BinaryTreeIteration {
    
        /**
         * 是否为对称树
         */
        public boolean isSymmetric(TreeNode root) {
    
            LinkedList<TreeNode> que = new LinkedList<>();
            que.addLast(root);
            que.addLast(root);
    
            while (!que.isEmpty()) {
                TreeNode root1 = que.removeFirst();
                TreeNode root2 = que.removeFirst();
                if (root1 == null && root2 == null) {
                    continue;
                } else if (root1 != null && root2 != null && root1.val == root2.val) {
                    que.addLast(root1.left);
                    que.addLast(root2.right);
                    que.addLast(root2.left);
                    que.addLast(root1.right);
                } else {
                    return false;
                }
            }
    
            return true;
        }
    
    }

### 二叉树实现 ###

/**
     * 二叉树实现
     * @author: mrBlackWhite
     * @data: 2020-07-07 11:38
     **/
    public class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    
        TreeNode(int x) {
            val = x;
        }
    
        @Override
        public String toString() {
            return Integer.toString(val);
        }
    
        // int []arr = {3, 9, 20, Integer.MAX_VALUE, Integer.MAX_VALUE, 15, 7};
        private static int[] StrToIntArray(String str) {
            str = str.substring(1, str.length() - 1);
            String[] strs = str.split(",");
            int[] arr = new int[strs.length];
            for (int i = 0; i < arr.length; i++) {
                if (strs[i].equals("null")) {
                    arr[i] = Integer.MAX_VALUE;
                } else {
                    arr[i] = Integer.parseInt(strs[i]);
                }
            }
    
            return arr;
        }
    
        // String str = "[3,9,20,null,null,15,7]";
        public static TreeNode makeTree(String str) {
    
            int[] arr = StrToIntArray(str);
            TreeNode[] nodes = new TreeNode[arr.length + 1];
            for (int i = 1; i < nodes.length; i++) {
                if (arr[i - 1] != Integer.MAX_VALUE) {
                    nodes[i] = new TreeNode(arr[i - 1]);
                } else {
                    nodes[i] = null;
                }
            }
            TreeNode node = null;
            for (int i = 1; i < nodes.length / 2; i++) {
                node = nodes[i];
                if (node == null) {
                    continue;
                }
                node.left = nodes[2 * i];
                node.right = nodes[2 * i + 1];
            }
            return nodes[1];
        }
    
        //中序遍历，检查树的创建是否正确
        public static void middleTraverse(TreeNode treeNode) {
            if (treeNode != null) {
                System.out.println(treeNode.val);
                middleTraverse(treeNode.left);
                middleTraverse(treeNode.right);
            } else {
                System.out.println("null");
            }
        }
    
        public static void main(String[] args) {
            String str = "[1,2,2,3,4,4,3]";
            TreeNode treeNode = TreeNode.makeTree(str);
            TreeNode.middleTraverse(treeNode);
        }
    }

### 测试类 ###

/**
     * 测试二叉树 迭代和递归两者的实现
     * @author: MrBlackWhite
     * @data: 2020-07-07 12:26
     **/
    public class Client {
    
        public static void main(String[] args) {
            String symmetric = "[1,2,2,3,4,4,3]";
            TreeNode treeSymmetric = TreeNode.makeTree(symmetric);
            System.out.println("递归_对称树测试" + new BinaryTreeRecurrence().isSymmetric(treeSymmetric));
            System.out.println("迭代_对称树测试" + new BinaryTreeIteration().isSymmetric(treeSymmetric));
    
            String nonSymmetric = "[1,2,2,null,3,null,3]";
            TreeNode treeNonSymmetric = TreeNode.makeTree(nonSymmetric);
            System.out.println("递归_非对称树测试" + new BinaryTreeRecurrence().isSymmetric(treeNonSymmetric));
            System.out.println("迭代_非对称树测试" + new BinaryTreeIteration().isSymmetric(treeNonSymmetric));
        }
    }