好的做蛋糕网站,创造与魔法官方网站一起做喜欢的事,扬州市建设厅网站,wordpress 短代码 插件1-leetcode94. 二叉树的中序遍历
注意#xff1a;√
递归方法已经很熟练了#xff0c;两种不同的递归方式迭代法需要注意#xff0c;zrm就遇到了要求迭代实现#xff0c;前序遍历和后续遍历其实不难#xff0c;中序遍历用的少#xff0c;注意看一看
// 1.递归方法1Lis…1-leetcode94. 二叉树的中序遍历
注意√
递归方法已经很熟练了两种不同的递归方式迭代法需要注意zrm就遇到了要求迭代实现前序遍历和后续遍历其实不难中序遍历用的少注意看一看
// 1.递归方法1ListInteger res new ArrayList();public ListInteger inorderTraversal(TreeNode root) {traverse(root);return res;}private void traverse(TreeNode root) {if (root null) {return;}traverse(root.left);// 中序位置res.add(root.val);traverse(root.right);}// 2.递归方法2public ListInteger inorderTraversal1(TreeNode root) {ListInteger res new ArrayList();if (root null) {return res;}res.addAll(inorderTraversal1(root.left));res.add(root.val);res.addAll(inorderTraversal1(root.right));return res;}// 3.迭代方法public ListInteger inorderTraversal2(TreeNode root) {ListInteger res new ArrayList();StackTreeNode stack new Stack();TreeNode cur root;while (cur ! null || !stack.isEmpty()) {if (cur ! null) {stack.add(cur);cur cur.left;}else {cur stack.pop();res.add(cur.val);cur cur.right;}}return res;}2-leetcode104. 二叉树的最大深度
注意√
动态规划思想秒杀 public int maxDepth(TreeNode root) {if (root null){return 0;}int leftDepth maxDepth(root.left);int rightDepth maxDepth(root.right);return Math.max(leftDepth, rightDepth) 1;}3-leetcode226. 翻转二叉树
注意√
递归的思想注意一下要提前保存左右的节点索引 public TreeNode invertTree(TreeNode root) {if (root null){return null;}TreeNode leftNode root.left;TreeNode rightNode root.right;root.left invertTree(rightNode);root.right invertTree(leftNode);return root;}4-leetcode101. 对称二叉树
注意×
建议直接使用队列的方式不过注意加入队列的方式很巧妙 左左右右 左右 右左 public boolean isSymmetric(TreeNode root) {LinkedListTreeNode queue new LinkedList();queue.add(root.left);queue.add(root.right);while (queue.size()0){TreeNode le queue.pollFirst();TreeNode ri queue.pollFirst();if (le null ri null){continue;}if (le null || ri null){return false;}if (le.val ! ri.val) {return false;}queue.add(le.left);queue.add(ri.right);queue.add(le.right);queue.add(ri.left);}return true;}5-leetcode543. 二叉树的直径
注意×
学习Labuladong这题可以由maxDepth转过来注意的地方是这个题目要的是二叉树的直径也就是路径值路径值和深度需要体会一下直径长就是左右两个深度加起来 int res 0;public int diameterOfBinaryTree(TreeNode root) {int x maxDepth(root);return res;}public int maxDepth(TreeNode root) {if (root null){return 0;}int leftDepth maxDepth(root.left);int rightDepth maxDepth(root.right);int curDepth leftDepth rightDepth;res Math.max(curDepth, res);return Math.max(leftDepth, rightDepth) 1;}6-leetcode102. 二叉树的层序遍历
注意××
注意加入queue的时候要判断是不是空while循环判断是不是空不要用size会浪费时间最开始就给res new LinkedList这样判断root null的时候可以直接返回结果 public ListListInteger levelOrder(TreeNode root) {ListListInteger res new LinkedList();if (root null){return res;}LinkedListTreeNode queue new LinkedList();queue.add(root);// while (queue.size()0){while (! queue.isEmpty()){int num queue.size();ListInteger list new LinkedList();for (int i 0; i num; i) {TreeNode node queue.poll();list.add(node.val);if (node.left ! null){queue.add(node.left);}if (node.right ! null){queue.add(node.right);}}res.add(list);}return res;}leetcode
注意√×
