可信验证网站,成品网站 免费,怎么写自己的网页,昆山网站建设jofuns链接力扣102-层序遍历
链接力扣102-层序遍历
思路#xff1a; 1、需要一个队列#xff0c;当一个队列出队时#xff0c;将其的孩子结点全部入队#xff1b; 2、每一层的结点数如何找到#xff1a;比如#xff0c;第一层root进入队列后#xff0c;得到len queue.size(…链接力扣102-层序遍历
链接力扣102-层序遍历
思路 1、需要一个队列当一个队列出队时将其的孩子结点全部入队 2、每一层的结点数如何找到比如第一层root进入队列后得到len queue.size(就循环让其出队的同时入队其孩子等到这一层出队完了其孩子结点也入队完了再次得到len就可以确定每层的结点数。
代码
class Solution {public ListListInteger levelOrder(TreeNode root) {ListListInteger res new ArrayList();// 创建暂存集合不应在这里创建应该在循环内这样每次循环都会有一个新的tmp集合// ListInteger tmp new ArrayList();QueueTreeNode queue new LinkedList();if(root null) return res;queue.offer(root);while(!queue.isEmpty()){int len queue.size();// 每次循环都会有一个新的tmp集合ListInteger tmp new ArrayList();// while(len 0){for(int i 0; i len; i){TreeNode node queue.poll();tmp.add(node.val);if(node.left ! null) queue.offer(node.left);if(node.right ! null) queue.offer(node.right);// len--;}res.add(tmp);}return res;}
}链接力扣226-翻转二叉树
思路 非递归 与层序遍历类似但是需要对每个出栈元素进行处理交换其左右孩子
class Solution {public TreeNode invertTree(TreeNode root) {QueueTreeNode queue new LinkedList();if(root null) return root;queue.offer(root);while(!queue.isEmpty()){int len queue.size();while(len 0){TreeNode node queue.poll();// 每一个出队的结点都要swap一下swap(node);if(node.left ! null) queue.offer(node.left);if(node.right ! null) queue.offer(node.right);len--;} }return root;}public void swap(TreeNode root){TreeNode node root.left;root.left root.right;root.right node;}
}递归 class Solution{public TreeNode invertTree(TreeNode root) {if (root null) return root;// swapChildren(root);// 左孩子的左右孩子交换右孩子的左右孩子交换invertTree(root.left);invertTree(root.right);// 再交换root的左右孩子swapChildren(root);// 此时左右孩子的孩子已经交换了root的左右孩子也交换了可以返回了return root;}private void swapChildren(TreeNode root) {TreeNode tmp root.left;root.left root.right;root.right tmp;}}链接力扣101-对称二叉树
思路 1、要比较的是两个节点
2、两个节点只要某一个为空或者两个值不等则不对称
3、节点的入队顺序相比较的节点要挨着入队 左节点的左孩子 右节点的右孩子 左节点的右孩子 右节点的左孩子 非递归 class Solution {public boolean isSymmetric(TreeNode root) {QueueTreeNode queue new LinkedList();queue.offer(root.left);queue.offer(root.right);while(!queue.isEmpty()){TreeNode leftnode queue.poll();TreeNode rightnode queue.poll();// 这里的continue继续下两个结点的弹出再进行循环比较if(leftnode null rightnode null) continue;if(leftnode null || rightnode null || leftnode.val ! rightnode.val){return false;} // 进队顺序//左节点的左孩子右节点的右孩子// 左节点的右孩子右节点的左孩子queue.offer(leftnode.left);queue.offer(rightnode.right);queue.offer(leftnode.right);queue.offer(rightnode.left);}return true;}
}递归 class Solution {public boolean isSymmetric(TreeNode root){// 1、参数和返回值不需要确认题目已给出// 2、递归终止条件return symmetric(root.left,root.right);}public boolean symmetric(TreeNode left,TreeNode right){// 终止条件在这里if(right null left null) return true;//这里一个细节必须先比较是否为空再比较值if((left null right ! null) ||(right null left ! null)||left.val ! right.val ) return false;// 两节点的孩子节点比较在这里return symmetric(left.left,right.right) symmetric(left.right,right.left);}
}
