【java】【python】leetcode刷题记录--二叉树
144.二叉树的前序遍历
题目链接
前、中、后的遍历的递归做法实际上都是一样的，区别就是遍历操作的位置不同。
对于先序遍历，也就是先根，即把查看当前结点的操作放在最前面即可。
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();preorder(root,res);return res;}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<>();midorder(root,res);return res;}public void midorder(TreeNode root, List<Integer> res){if(root == null){return;}midorder(root.left,res);res.add(root.val);midorder(root.right,res);}
}
//后序
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();postorder(root,res);return res;}public void postorder(TreeNode root, List<Integer> res){if(root == null){return;}postorder(root.left,res);postorder(root.right,res);res.add(root.val);}
}
python版本也一样，这里就写一种：
class Solution:def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:res = []def dfs(root):if root is None:return dfs(root.left)dfs(root.right)res.append(root.val)dfs(root) # 调用dfs函数开始遍历return res
如果不用递归，那会有一点麻烦，但也仅仅是代码上的。因为递归本身就是借用系统栈，而使用迭代则是自己创建栈进行操作即可。
前序则是将根节点入栈，后续的结点是按照先右边再左边的顺序入栈（因为我们要先处理左子，因此左子后入栈可以先被pop）。
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();if (root == null){return res;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while(!stack.isEmpty()){TreeNode tmp = stack.pop();res.add(tmp.val);if(tmp.right != null){stack.push(tmp.right);}if(tmp.left != null){stack.push(tmp.left);}}return res;}
}
但中后序的操作和前序不太一样（虽然有方法可以进行统一，但本文不赘述）。而后序则是将先序（根左右）进行操作（根左右->根右左->左右根），即调整处理顺序+反转数组。
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;}
}
102 二叉树的层序遍历
题目链接
层序遍历用的是队列，每次将一个节点入队，处理完当前节点，则其子节点分别入队，下一轮再处理子节点，也就是下一层的内容。
例如，一棵树为1、2、3、4、5（数组表示），那么第一次是1入队，处理完1后，1的子节点也就是2、3入队。处理完2，也就是2的子节点入队，即4、5。3处理后没有子节点，就剩下4、5需要处理。
如果是要求返回的是一个列表，没有嵌套结构，那就会好做很多，我们就按照上面的流程构造队列然后不断处理即可。但现在返回的要求是每一层都要有一个单独的列表，因此就麻烦一些。
我们就使用两重循环，第一重是记录队列是否为空，第二重则是看当前遍历的层。
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<TreeNode> deque = new LinkedList<>();List<List<Integer>> res = new ArrayList<List<Integer>>();if(root == null){return res;}deque.add(root);while(!deque.isEmpty()){// len记录当前层的个数，tmpList则是存放当前层，最后统一add到res上int len = deque.size();List<Integer> tmpList = new ArrayList<>();while(len>0){TreeNode tmpNode = deque.removeFirst();tmpList.add(tmpNode.val);if(tmpNode.left!=null){deque.add(tmpNode.left);}if(tmpNode.right!=null){deque.add(tmpNode.right);}len--;}res.add(tmpList);}return res;}
}