代码随想录算法训练营第十五天|● 层序遍历 10 ● 226.翻转二叉树 ● 101.对称二叉树 2

102.二叉树的层序遍历

力扣题目链接(opens new window)

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

思路：

迭代法，非递归思路，借用队列，先进先出来达到层序遍历的效果。但写的过程中，我不知道该如何让同一层的数据都保存在一个数组里。

看了题解发现，可以用队列的长度len来表达同一层的节点个数，当len>0，那么节点的所有数值都保存在一个数组中。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Deque<TreeNode> deq = new LinkedList<>();
        if(root == null) return res;
        deq.offer(root);
        while(!deq.isEmpty()){
            List<Integer> res1 = new ArrayList<>();
            int len = deq.size();
            while(len > 0){
                TreeNode node = deq.poll();
                res1.add(node.val);
                if(node.left != null) deq.offer(node.left);
                if(node.right != null) deq.offer(node.right);
               
                len--;
            }
            res.add(res1);
        }
        return res;
    }
}

226.翻转二叉树

力扣题目链接(opens new window)

翻转一棵二叉树。

这道题目背后有一个让程序员心酸的故事，听说 Homebrew的作者Max Howell，就是因为没在白板上写出翻转二叉树，最后被Google拒绝了。（真假不做判断，权当一个乐子哈）

思路：

递归法稍微好理解一些，根据前后序遍历，先反转左右孩子，再反转左右子树。

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) return null;
        invertTree(root.left);
        invertTree(root.right);
        swap(root);
        return root;
    }

    void swap(TreeNode root){
        TreeNode tmp = root.right;
        root.right = root.left;
        root.left = tmp;
    }
}

101. 对称二叉树

力扣题目链接(opens new window)

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

思路：

镜像对称，外侧对外侧，内侧对内侧，递归判断是否对称。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return compare(root.left, root.right);
    }
    boolean compare(TreeNode left, TreeNode right){
        if(left != null && right == null){
            return false;
        }
        if(left == null && right != null){
            return false;
        }
        if(left == null && right == null){
            return true;
        }
        if(left.val != right.val){
            return false;
        }
        boolean compareoutside = compare(left.left, right.right);
        boolean compareinside = compare(left.right, right.left);
        return compareinside && compareoutside;
    }
 }