网站建设运营公司推荐,西湖南昌网站建设公司,门户网站如何建设方案,wordpress启用收费下载无效二叉树层序遍历
题目链接#xff1a;102. 二叉树的层序遍历
思路#xff1a;利用队列来存储遍历的节点#xff0c;同时要定义size来保存当前层的节点个数。
时间复杂度O(n)
层序遍历的一般写法#xff0c;通过一个 while 循环控制从上向下一层层遍历#xff0c;for 循…二叉树层序遍历
题目链接102. 二叉树的层序遍历
思路利用队列来存储遍历的节点同时要定义size来保存当前层的节点个数。
时间复杂度O(n)
层序遍历的一般写法通过一个 while 循环控制从上向下一层层遍历for 循环控制每一层从左向右遍历。
class Solution {public ListListInteger levelOrder(TreeNode root) {ListListInteger res new LinkedList();if (root null) {return res;}QueueTreeNode q new LinkedList();q.offer(root);// while 循环控制从上向下一层层遍历while (!q.isEmpty()) {// 存储当前层的节点个数int sz q.size();// 记录这一层的节点值ListInteger level new LinkedList();// for 循环控制每一层从左向右遍历for (int i 0; i sz; i) {TreeNode cur q.poll();level.add(cur.val);if (cur.left ! null)q.offer(cur.left);if (cur.right ! null)q.offer(cur.right);}res.add(level);}return res;}
}226.反转二叉树
题目链接226. 翻转二叉树
思路可以用层序遍历实现前序和后序的递归遍历也可以实现中序的递归遍历实现逻辑较为复杂不推荐。迭代遍历也可以实现。注意是交换节点的左右子树改变指针指向而不是交换左右孩子的值。
层序遍历实现
class Solution {public TreeNode invertTree(TreeNode root) {if (root null) return null;QueueTreeNode que new LinkedList();que.add(root);while (!que.isEmpty()) {TreeNode node que.poll();TreeNode temp node.left;node.left node.right;node.right temp;if (node.left ! null) {que.add(node.left);}if (node.right ! null) {que.add(node.right);}}return root;}
}前序递归遍历实现。
class Solution {public TreeNode invertTree(TreeNode root) { // 递归前序实现if (root null) return null;TreeNode temp root.left;root.left root.right;root.right temp;invertTree(root.left);invertTree(root.right);return root;}
}后序递归遍历实现。
class Solution {public TreeNode invertTree(TreeNode root) { // 递归后序实现if (root null) return null;invertTree(root.left);invertTree(root.right);TreeNode temp root.left;root.left root.right;root.right temp;return root;}
}101.对称二叉树
题目链接101. 对称二叉树
思路该题其实是判断两棵树是否相同只能采用后序遍历。根节点的左子树的遍历顺序为左、右、中根节点的右子树的遍历顺序为右、左、中都可以理解为后序遍历。
class Solution {public boolean isSymmetric(TreeNode root) {if (root null) return true;// 检查两棵子树是否对称return check(root.left, root.right);}boolean check(TreeNode left, TreeNode right) {if (left null || right null) return left right;// 两个根节点需要相同if (left.val ! right.val) return false;// 左右子节点需要对称相同return check(left.right, right.left) check(left.left, right.right);}
}另一种写法
class Solution {public boolean isSymmetric(TreeNode root) {return compare(root.left, root.right);}private boolean compare(TreeNode left, TreeNode right) {if (left null || right null) {if (left null right null) {return true;} else {return false;}}if (left.val ! right.val) return false;boolean outside compare(left.left, right.right);boolean inside compare(left.right, right.left);return outside inside;}
}递归三部曲 1、确定递归函数的参数和返回值。 2、确定终止条件。 3、确定单层递归的逻辑。
