Day 14 | 层序遍历、226.翻转二叉树、101.对称二叉树

层序遍历

借助队列，
遍历树，将一层节点全部入队后，记录队内元素个数 len，出队 len 个元素，即该层元素遍历完毕，遍历过程中将下一层节点全部入队。

代码：

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();

    Deque<TreeNode> que = new LinkedList<>();

    if (root != null) que.offerLast(root);
    

    while (!que.isEmpty()) {
        List<Integer> list = new ArrayList<>();

        que.offerLast(null);
        TreeNode node = que.poll();
        
        while (node != null) {
            list.add(node.val);

            if (node.left != null) que.offerLast(node.left);
            if (node.right != null) que.offerLast(node.right);

            node = que.poll();
        }
        res.add(list);
    }
    
    return res;
}
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

226.翻转二叉树

思路：
翻转二叉树，即需要交换每个节点的左右孩子。
采用的递归的思路，依次翻转每个节点的左右孩子。

public TreeNode invertTree(TreeNode root) {
	if (root == null) return root;
	
	swap(root.left, root.right); // 自己定义交换左右节点
	invertTree(root.left);
	invertTree(root.right);
	
	return root;
}
1
2
3
4
5
6
7
8
9

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

    TreeNode temp = root.left;
    root.left = invertTree(root.right);
    root.right = invertTree(temp);

    return root;
    
}
1
2
3
4
5
6
7
8
9
10

101.对称二叉树

思路：参考代码随想录
首先想清楚，判断对称二叉树要比较的是哪两个节点，要比较的可不是左右节点！

对于二叉树是否对称，要比较的是根节点的左子树与右子树是不是相互翻转的，理解这一点就知道了其实我们要比较的是两个树（这两个树是根节点的左右子树），所以在递归遍历的过程中，也是要同时遍历两棵树。

那么如何比较呢？

比较的是两个子树的里侧和外侧的元素是否相等。如图所示：

public class LC101_isSymmetric {
    // 对称二叉树
    public boolean isSymmetric(TreeNode root) {
        // 递归法
        return compare(root.left, root.right);
    }

    private boolean compare(TreeNode left, TreeNode right) {
        if (left != null && right == null) return false;
        else if (left == null && right != null) return false;
        // 左右为空时，返回true；
        else if (left == null && right == null) return true;
        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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20