对称二叉树

发表于
本文字数： 3.8k 阅读时长 ≈ 3 分钟

LeetCode每日一题，101.Symmetric Tree

先看题目描述

大意就是题目给定一个二叉树，让我们判定这是否是一个对称二叉树

算法和思路

这道题我一开始是往先序遍历、中序遍历方向去想，然后发现对称二叉树的中序遍历序列是对称的，于是先试着实现了一下，发现这只是必要条件，不是充分条件，除了中序遍历序列对称，还需满足其他条件才是对称二叉树。于是又往先序遍历序列方向考虑，最后发现当对根节点的左子树进行根左右的遍历，对根节点的右子树进行根右左的遍历时，会满足一定规律，以图中例子为例，该二叉树中序遍历得到序列为 [3, 2, 4, 1, 4, 2, 3]，对根节点的左子树进行根左右的遍历，右子树进行根右左的遍历，得到序列为 [1, 2, 3, 4, 2, 3, 4]

最后得到规律为中序遍历序列要满足 nodes[i] = nodes[len - i -1] (i >= 0)，另一序列要满足 nodes[i] = nodes[i + (len - 1)/2] (i >= 1)，这时便是对称二叉树

下面是实现源码

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
import java.util.ArrayList;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    ArrayList<Integer> preNodes = new ArrayList<>();
    ArrayList<Integer> inNodes = new ArrayList<>();

   public void preOrderTraversal(TreeNode root) {
        preNodes.add(root.val);
        if (root.left != null) leftOrderTraversal(root.left);
        else if (root.right != null) preNodes.add(null);
        if (root.right != null) rightOrderTraversal(root.right);
        else if (root.left != null) preNodes.add(null);
    }

    public void leftOrderTraversal(TreeNode root) {
        preNodes.add(root.val);
        if (root.left != null) leftOrderTraversal(root.left);
        else if (root.right != null) preNodes.add(null);
        if (root.right != null) leftOrderTraversal(root.right);
        else if (root.left != null) preNodes.add(null);
    }
    
    public void rightOrderTraversal(TreeNode root) {
        preNodes.add(root.val);
        if (root.right != null) rightOrderTraversal(root.right);
        else if (root.left != null) preNodes.add(null);
        if (root.left != null) rightOrderTraversal(root.left);
        else if (root.right != null) preNodes.add(null);
    }

    public void InOrderTraversal(TreeNode root) {
        if (root.left != null) InOrderTraversal(root.left);
        else if (root.right != null) inNodes.add(null);
        inNodes.add(root.val);
        if (root.right != null) InOrderTraversal(root.right);
        else if (root.left != null) inNodes.add(null);
    }

    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        inNodes.clear();
        InOrderTraversal(root);
        preOrderTraversal(root);
        System.out.println(preNodes);
        System.out.println(inNodes);
        int len = inNodes.size();
        if (len == 1) return true;
        int left = (len + 1)/2 - 1;
        int right = (len + 2)/2 - 1;
        while (left >= 0) {
            if (inNodes.get(left) != inNodes.get(right)) return false;
            left--;
            right++;
        }
        left = 1;
        right = left + (len - 1)/2;
        while (right < len) {
            if (preNodes.get(left) != preNodes.get(right)) return false;
            left++;
            right++;
        }
        return true;
    }
}

后面看题解时发现我这方法太麻烦了，从一开始方向就想错了，直接用递归来判断是否是对称二叉树就可以，效率高，代码简洁

递归结束条件：

  • 当两个指针都为空时，返回 true
  • 当只有一个指针为空时，返回 false

递归过程：

  • 判断两个指针当前节点值是否相等
  • 判断 A 的左子树是否与 B 的右子树对称
  • 判断 A 的右子树是否与 B 的左子树对称

下面是算法的实现源码，代码中对 && 的运用十分巧妙，并且灵活运用了短路，使得代码十分简洁，且运行效率较高，这种对 && 和短路的运用很值得学习

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.ArrayList;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isMirror(root, root);
    }

    public boolean isMirror(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) return true;
        if(t1 == null || t2 == null) return false;
        return (t1.val == t2.val) && isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);
    }
}