Day15.二叉树part02： 层序遍历、226.翻转二叉树 、 101. 对称二叉树

本文主要是介绍Day15.二叉树part02： 层序遍历、226.翻转二叉树 、 101. 对称二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Day15.二叉树part02： 层序遍历、226.翻转二叉树 、 101. 对称二叉树

102.二叉树的层序遍历

原题链接

代码随想录链接

刚开始看的时候感觉不会写，因为一直对树的算法题很抵触就是感觉自己搞不明白，不过现在就感觉干就完了！

不会写的时候去看了卡哥的解析，当提示到可以使用队列来写的时候我脑子里就瞬间有了想法，这不是和昨天的二叉树迭代遍历有点类似吗，于是自己去想好了思路写完代码果然通过了。

思路如下：

• 创建一个队列用于顺序存放每一层的元素
• 先将树的根节点放入队列后开始一个while循环，循环终止的条件是队列为空；
• while循环里先定义一个size用于代表当前队列的长度，然后在定义一个List集合用于存放每层的节点的val值并最终将它们放入结果集合中；
• 之后再内嵌一个while循环，终止条件为size等于0时代表已经遍历完了当前这层树的节点；
• 内嵌循环中先将队列头结点出队，并将出队节点的val值存入到小集合中，然后再判断出队节点是否有左右孩子，如果有的话也将它们加入队列中
• 内嵌循环结束后小集合添加到结果集合中，最后返回最终结果集合；

java源代码如下：

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

226.反转二叉树

原题链接

代码随想录链接

本题可以用递归和迭代两种方式做，我们先来看第一种方法

递归法

这里用到的是后序遍历递归，先遍历左节点，然后遍历右节点，最后把父节点的左右子树交换。

java代码如下：

class Solution {public TreeNode invertTree(TreeNode root) {if(root == null){return root;}invertTree(root.left);invertTree(root.right);swapNode(root);return root;}public void swapNode(TreeNode node){TreeNode temp = node.left;node.left = node.right;node.right = temp;}
}

迭代法

用递归可以做的用栈也可以做！

步骤如下：

1.新建一个栈并让根节点入栈如下图

2.让栈顶元素出栈，并交换该元素的左右孩子后，将它的左右孩子也入栈，如下图

3.之后再将栈顶元素出栈，这样一直循环直到栈内为空

java代码如下：

class Solution {public TreeNode invertTree(TreeNode root) {if(root == null){return root;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while(!queue.isEmpty()){TreeNode node = queue.poll();swapNode(node);if(node.left != null) queue.offer(node.left);if(node.right != null) queue.offer(node.right);}return root;}public void swapNode(TreeNode node){TreeNode temp = node.left;node.left = node.right;node.right = temp;}
}

本题也可以用层序遍历来写，也就是依靠队列。

101.对称二叉树

原题链接

代码随想录链接

本题可以用递归和迭代两种方法，这里只写迭代的具体实现

1.先定义一个普通队列，然后将根节点的左右孩子加入队列中，如下图

2.接着while循环，当队列为空时退出循环，循环里先将queue的前两个元素poll出去，并分别定义为左节点和右节点，如下图

3.然后进行判断两节点是否相等等等这些因素，再把左节点的左孩子、右节点的右孩子、左节点的右孩子，右节点的左孩子按顺序加入队列，如下图

4.之后直到循环结束

java代码如下：

class Solution {public boolean isSymmetric(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();queue.offer(root.left);queue.offer(root.right);while(!queue.isEmpty()){TreeNode left = queue.poll();TreeNode right = queue.poll();//这里应该为continue而不是return trueif(left == null && right == null){continue;//判断条件注意}else if(left == null || right == null || left.val != right.val){return false;}queue.offer(left.left);queue.offer(right.right);queue.offer(left.right);queue.offer(right.left);}return true;}
}

        queue.offer(left.left);queue.offer(right.right);queue.offer(left.right);queue.offer(right.left);}return true;
}

}

这篇关于Day15.二叉树part02： 层序遍历、226.翻转二叉树 、 101. 对称二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---