[LeetCode]树问题代码总结(一)

101 对称二叉树

  1. 递归

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    public boolean isSymmetric(TreeNode root) {
            if (root == null) return true;
            return symmetric(root.left, root.right);
        }
    private boolean symmetric (TreeNode leftNode, TreeNode rightNode) {
            if (leftNode == null && rightNode == null) return true;
            else if (leftNode == null || rightNode == null) return false;

            if (leftNode.val != rightNode.val) return false;
            return symmetric(leftNode.left, rightNode.right) && symmetric(leftNode.right, rightNode.left);
        }

  2. 迭代 - 根本思想不变，依然是比较leftNode.right.value == rightNode.val. 不需要把root入队，让root.left和root.right入队，作为队列前2元素，出队比较，若相同，将leftNode.right和rightNode.left、leftNode.left和rightNode.right分别作为pair入队即可。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    public boolean isSymmetric(TreeNode root) {
            if (root == null) return true;
            Queue<TreeNode> q = new LinkedList<>();
            q.add(root.left);
            q.add(root.right);
            while (!q.isEmpty()) {
                TreeNode node1 = q.poll();
                TreeNode node2 = q.poll();
                if (node1 == null && node2 == null) continue; // 【不能直接 return true】
                if (node1 == null && node2 != null) return false;
                if (node1 != null && node2 == null) return false;
                if (node1.val != node2.val) return false;
                q.add(node1.left);
                q.add(node2.right);
                q.add(node1.right);
                q.add(node2.left);
            }
            return true;
        }

树的翻转问题

226 翻转二叉树 [EASY]

简单的递归解法，没有写迭代法。

1
2
3
4
5
6
7
public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;
        TreeNode temp = invertTree(root.left);
        root.left = invertTree(root.right);
        root.right = temp;
        return root;
    }

951 翻转等价二叉树 [MEDIUM]

1
2
3
4
5
6
7
8
9
public boolean flipEquiv(TreeNode root1, TreeNode root2) {
        if(root1 == null && root2 == null) return true;
        if (root1 == null || root2 == null) return false;
        if (root1.val != root2.val) return false;

        boolean no_flip = flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right);
        boolean flip = flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left);
        return no_flip || flip;
    }

971 翻转二叉树以匹配先序遍历 [MEDIUM]

  • 因为是先序遍历，所以voyage[++index]的对应的是当前结点的左孩子current.left对应的值，若current.left.val与该值不符，就先交换左右结点（不管交换后是否对应）。然后递归先左后右（先序）。
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
private int idx = 0; // 记录当前 voyage 的index
    private List<Integer> res = new ArrayList<>();
    private boolean flag = false; // 记录当前二叉树是否能通过翻转匹配先序遍历
    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        flip(root, voyage);
        if (flag) return Arrays.asList(-1);
        else return res;
    }
    private void flip (TreeNode root, int[] voyage) {
        if (root == null) return;
        if (root.val != voyage[idx++]) {
            flag = true;
            return;
        }
        else {
            if (root.left != null && root.left.val != voyage[idx]) {// 当前结点需要翻转
                TreeNode temp = root.left;
                root.left = root.right;
                root.right = temp;
                res.add(root.val); // 翻转了的加入List中
            }
        }
        flip(root.left, voyage);
        flip(root.right, voyage);
    }