二叉树遍历/算法数据结构
六、树
6.1遍历算法
6.1.1前中后序
-
在做递归时,最重要是三步骤
-
确定递归函数的返回值和参数
-
确定终止条件
-
确定单层递归的逻辑
伪代码 void travel(cur, vec) {if (cur == null) {return ;}vec.push(cur->middle, vec); // 递归中节点vec.push(cur->left, vec); // 递归左节点vec.push(cur->right, vec); // 递归右节点 }
-
其实很简单,参数就是要目前遍历节点在哪,返回值也同理,终止条件就是指遍历到null的时候回溯,逻辑不要想复杂,根据顺序移动上述上个递归函数即可
-
前顺遍历
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();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;}public void inorder(TreeNode root, List<Integer> res) {if (root == null) {return;}inorder(root.left, res);res.add(root.val);inorder(root.right, res);} }
-
后序遍历
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();postorder(root, result);return result;}public void postorder(TreeNode root, List<Integer> result) {if (root == null) {return;}postorder(root.left, result); postorder(root.right, result);result.add(root.val);} }
-
其实很简单,根据遍历的顺序摆放遍历顺序和添加元素的顺序,(root.left, result)代表左子树,(root.right, result)代表右子树,(root.val)代表中节点。
-
递归
-
前序(要理解遍历的核心,先把中节点塞入,然后根据栈去模拟,先加入右节点然后是左节点,移动到左节点继续加入)
class Solution {public List<Integer> preorderTraversal(TreeNode root) {Stack<TreeNode> stack = new Stack<>();List<Integer> res = new ArrayList<>();if (root == null){return res;}stack.push(root);while (!stack.isEmpty()) {TreeNode temp = stack.pop();res.add(temp.val);if (temp.right != null) {stack.push(temp.right);}if (temp.left != null) {stack.push(temp.left);}}return res;} }
-
中序(核心就是每收集一个元素到res数组中,其实都是以中节点的姿态进入,这也对应了为什么if循环为什么要push一个null节点,前中后也只要交换顺序即可)
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();if (root != null) stack.push(root);while (!stack.isEmpty()) {TreeNode temp = stack.peek();if (temp != null) {stack.pop();if (temp.right != null) stack.add(temp.right);stack.push(temp);stack.push(null);if (temp.left != null) stack.add(temp.left);}else {stack.pop();temp = stack.peek();stack.pop();res.add(temp.val);}}return res;} }
-
后序(就是前序遍历的左右调换顺序,然后再倒叙结果数组)
class Solution {public List<Integer> postorderTraversal(TreeNode root) {Stack<TreeNode> stack = new Stack<>();List<Integer> res = new ArrayList<>();if (root == null){return res;}stack.push(root);while (!stack.isEmpty()) {TreeNode temp = stack.pop();res.add(temp.val);if (temp.left != null) {stack.push(temp.left);}if (temp.right != null) {stack.push(temp.right);}}Collections.reverse(res);return res;} }
-
6.1.2层序遍历
-
递归算法,一般递归就是深度优先了,要明确三要素,一般遍历就是参数为当前处理节点+加其它附属条件,循环处理按照顺序(这里是左到右),结束条件都是到底直接返回
class Solution {List<List<Integer>> res = new ArrayList<List<Integer>>();public List<List<Integer>> levelOrder(TreeNode root) {check(root, 0);return res;}public void check(TreeNode temp, int deep) {if (temp == null) {return;}deep++;if (res.size() < deep) { // 创建数组的条件,不可能预先创建的List<Integer> res1 = new ArrayList<>();res.add(res1);}res.get(deep-1).add(temp.val); // 注意为deep-1,区分索引和深度的区别check(temp.left, deep); // 左子树check(temp.right, deep); // 右子树} }
-
迭代,就是按照队列,先进先出,按照层数模拟也就是广度优先遍历
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {Deque<TreeNode> queue = new ArrayDeque<>();List<List<Integer>> res = new ArrayList<List<Integer>>(); // 结果二维数组if (root != null) {queue.addLast(root); // 防止root为空}while (!queue.isEmpty()) {int size = queue.size(); // size代表每一层几个元素List<Integer> res1 = new ArrayList<>();while (size > 0) { // size为0这一层就停止TreeNode temp = queue.removeFirst();res1.add(temp.val);if (temp.left != null) queue.addLast(temp.left); // 左节点if (temp.right != null) queue.addLast(temp.right); // 右节点size--; // 记得减一}res.add(res1);}return res;} }