代码随想录算法训练营第十五天 | 二叉树的层序遍历、翻转二叉树、对称二叉树

层序遍历

leetcode
文档题解
视频题解

巧用 size，分层记录节点。如果是直接输出，不用分层展示，就不需要 size。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new LinkedList<>();
        Queue<TreeNode> q = new LinkedList<>();

        if (root != null) {
            q.offer(root);
        }

        while (!q.isEmpty()) {
            // 记录当前层有多少节点
            int size = q.size();
            List<Integer> level = new LinkedList<>();

            while (size > 0) {
                TreeNode node = q.poll();
                level.add(node.val);
                // 追加下一层的节点
                if (node.left != null) {
                    q.offer(node.left);
                }
                if (node.right != null) {
                    q.offer(node.right);
                }
                size--;
            }

            // 收集当前层的节点
            list.add(level);
        }

        return list;
    }
}

226. 翻转二叉树

leetcode
文档题解
视频题解

递归解法，先深入到最底层进行交换，然后不断向上返回子树的根。

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;

        // 先处理左右孩子
        if (root.left != null) {
            invertTree(root.left);
        }

        if (root.right != null) {
            invertTree(root.right);
        }

        // 然后交换当前子树的左右孩子
        TreeNode tmp = root.right;
        root.right = root.left;
        root.left = tmp;

        // 返回当前子树的根
        return root;
    }
}

101. 对称二叉树

leetcode
文档题解
视频题解

判断二叉树是否对称的方法就是判断两棵子树的内外侧是否相等，因此要同时遍历两棵树。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return compare(root.left, root.right);
    }

    // 比较两棵子树的内外侧是否相等
    public boolean compare(TreeNode left, TreeNode right) {
        // 节点为空 & 节点不为空但值不相等的情况
        if (left == null && right == null) return true;
        else if (left == null && right != null) return false;
        else if (left != null && right == null) return false;
        else if (left.val != right.val) return false;

        // 节点不为空 & 值相等
        // 于是比较两棵树的内外侧是否相等
        boolean outside = compare(left.left, right.right);
        boolean inside = compare(left.right, right.left);
        return outside && inside;
    }
}

按照上面的方法，稍加修改也可以判断两棵树是否相等。

100. 相同的树

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        else if (p == null && q != null) return false;
        else if (p != null && q == null) return false;
        else if (p.val != q.val) return false;

        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}