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; } }
![](/images/780-200-2.jpg)