当前位置：首页 > news >正文

（二刷）代码随想录第15天|层序遍历 226.翻转二叉树 101.对称二叉树2

news 来源：原创 2024/6/28 19:43:36

层序遍历 10

102. 二叉树的层序遍历 - 力扣（LeetCode）

代码随想录 (programmercarl.com)

综合代码：

class Solution{public List<List<Integer>> resList = new ArrayList<List<Integer>>();public List<List<Integer>> levelOrder(TreeNode root){checkFund02(root);return resList;}public void checkFund02(TreeNode node){if(node == null) return;//创建一个队列，用于存储待处理的节点Queue<TreeNode> que = new LinkedList<TreeNode>();que.offer(node);while(!que.isEmpty()){List<Integer> itemList = new ArrayList<Integer>();int len = que.size();for(int i = 0; i<len; i++){TreeNode tmpNode = que.poll();itemList.add(tmpNode.val);if(tmpNode.left != null) que.offer(tmpNode.left);if(tmpNode.right != null) que.offer(tmpNode.right);}resList.add(itemList);}}
}

226.翻转二叉树

226. 翻转二叉树 - 力扣（LeetCode）

代码随想录 (programmercarl.com)

翻转一棵二叉树。

这道题不能使用中序遍历，因为会翻转2次，我使用的是后序遍历：

//确定参数的返回值
public TreeNode invertTree(TreeNode root){//确定终止条件    if(root == null){return null;}//确定单层递归的逻辑：//后序遍历翻转二叉树invertTree(root.left);invertTree(root.right);invertTree(root);return root;
}//定义一个私有方法，用于交换给定节点的左右孩子
private void swapChildren(TreeNode root){TreeNode tmp = root.left;root.left = root.right;root.right = tmp;
}

更简洁版本：

class Solution {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;}
}

101.对称二叉树 2

class Solution {public boolean isSymmetric(TreeNode root) {if(root==null || (root.left==null && root.right==null)) {return true;}//用队列保存节点LinkedList<TreeNode> queue = new LinkedList<TreeNode>();//将根节点的左右孩子放到队列中queue.add(root.left);queue.add(root.right);while(queue.size()>0) {//从队列中取出两个节点，再比较这两个节点TreeNode left = queue.removeFirst();TreeNode right = queue.removeFirst();//如果两个节点都为空就继续循环，两者有一个为空就返回falseif(left==null && right==null) {continue;}if(left==null || right==null) {return false;}if(left.val!=right.val) {return false;}//将左节点的左孩子， 右节点的右孩子放入队列queue.add(left.left);queue.add(right.right);//将左节点的右孩子，右节点的左孩子放入队列queue.add(left.right);queue.add(right.left);}return true;}
}