在之前刷力扣的过程中,我每刷道题都是先看题解然后再去边写边看,很多内容根本没消化,在进度上欺骗自己,感觉之前刷的都忘了,能力没有什么提升,现在还是一道都不会做。所以这次报了卡哥的算法训练营,希望能够按计划地有效刷题。本次刷题,我用的是 Java 语言解题,有余力的话也可能会加上 C++ 的题解。以下是算法训练营第十五天的刷题记录和思考笔记。
一、102 二叉树层序遍历 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 class Solution { public List<Integer> preorderTraversal (TreeNode root) { List<Integer> result = new ArrayList <Integer>(); preorder(root, result); return result; } public void preorder (TreeNode root, List<Integer> result) { if (root == null ) { return ; } result.add(root.val); preorder(root.left, result); preorder(root.right, result); } } class Solution { public List<Integer> inorderTraversal (TreeNode root) { List<Integer> res = new ArrayList <>(); inorder(root, res); return res; } void inorder (TreeNode root, List<Integer> list) { if (root == null ) { return ; } inorder(root.left, list); list.add(root.val); inorder(root.right, list); } } class Solution { public List<Integer> postorderTraversal (TreeNode root) { List<Integer> res = new ArrayList <>(); postorder(root, res); return res; } void postorder (TreeNode root, List<Integer> list) { if (root == null ) { return ; } postorder(root.left, list); postorder(root.right, list); list.add(root.val); } }
三、二叉树的迭代遍历 递归的实现就是:每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中,然后递归返回的时候,从栈顶弹出上一次递归的各项参数,所以这就是递归为什么可以返回上一层位置的原因。
因此,我们可以用迭代法(非递归的方式)来实现二叉树的前后中序遍历。
前序遍历是中左右,每次先处理的是中间节点,那么先将根节点放入栈中,然后将右孩子加入栈,再加入左孩子。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public List<Integer> preorderTraversal (TreeNode root) { List<Integer> result = new ArrayList <>(); if (root == null ){ return result; } Stack<TreeNode> stack = new Stack <>(); stack.push(root); while (!stack.isEmpty()){ TreeNode node = stack.pop(); result.add(node.val); if (node.right != null ){ stack.push(node.right); } if (node.left != null ){ stack.push(node.left); } } return result; } }
中序遍历是左中右,先访问的是二叉树顶部的节点,然后一层一层向下访问,直到到达树左面的最底部,再开始处理节点(也就是在把节点的数值放进 result 数组中),这就造成了处理顺序和访问顺序是不一致的。那么在使用迭代法写中序遍历,就需要借用指针的遍历来帮助访问节点,栈则用来处理节点上的元素。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public List<Integer> inorderTraversal (TreeNode root) { List<Integer> result = new ArrayList <>(); if (root == null ){ return result; } Stack<TreeNode> stack = new Stack <>(); TreeNode cur = root; while (cur != null || !stack.isEmpty()){ if (cur != null ){ stack.push(cur); cur = cur.left; }else { cur = stack.pop(); result.add(cur.val); cur = cur.right; } } return result; } }
再来看后序遍历,先序遍历是中左右,后续遍历是左右中,那么我们只需要调整一下先序遍历的代码顺序,就变成中右左的遍历顺序,然后在反转 result 数组,输出的结果顺序就是左右中了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public List<Integer> postorderTraversal (TreeNode root) { List<Integer> result = new ArrayList <>(); if (root == null ){ return result; } Stack<TreeNode> stack = new Stack <>(); stack.push(root); while (!stack.isEmpty()){ TreeNode node = stack.pop(); result.add(node.val); if (node.left != null ){ stack.push(node.left); } if (node.right != null ){ stack.push(node.right); } } Collections.reverse(result); return result; } }