代码随想录算法训练营||二叉树

前/中/后序遍历

递归方式

参考文章

题目

思路：其实递归方式的前中后序遍历的方式都差不多，区别是在父节点的遍历时间。

前序代码

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> result = new ArrayList<>();inorder(root, result);return result;}public void inorder(TreeNode root, List<Integer> result) {if (root == null) {return;}inorder(root.left, result);result.add(root.val);inorder(root.right, result);}}

题目

后序代码

  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);             // 注意这一句}

层序遍历

题目

参考文章

思路：层序遍历就是把二叉树中一层一层的存储起来，这里我们用队列的方式来暂时存储每一层的元素（主要用于while循环时，size大小的固定），然后添加到一个一维数组中，最后以二维数组的方式就可以得到每一层的数据了

代码

class Solution {public List<List<Integer>> resList = new ArrayList<List<Integer>>();public List<List<Integer>> levelOrder(TreeNode root) {checkFun02(root);return resList;}public void checkFun02(TreeNode node) {if(node==null){return;}Queue<TreeNode> que = new LinkedList<TreeNode>();que.offer(node);while(!que.isEmpty()){List<Integer> itemList = new ArrayList<Integer>();int size = que.size();while(size>0){TreeNode tempNode=que.poll();itemList.add(tempNode.val);if(tempNode.left!=null){que.offer(tempNode.left);}if(tempNode.right!=null){que.offer(tempNode.right);}size--;}resList.add(itemList);   }}
}