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

102.二叉树的层序遍历

扣除主题链接(opens new window)

给你一棵二叉树，请返回它 层序遍历 获得的节点值。 (即从左到右逐层访问所有节点)。

思路：

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

查看问题解决方案后，发现同一层的节点数可以用队列的长度len来表达，当len>然后节点的所有值都保存在一个数组中。

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)

翻转一棵二叉树。

这个话题背后有一个让程序员难过的故事。我听说 Maxmebrew作者 Howell，因为没有在白板上写翻转二叉树，最后被谷歌拒绝了。(真假不做判断，权当乐子哈)

思路：

递归法更容易理解。根据前后顺序，先将左右儿童逆转，再将左右子树逆转。

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;    } }