学习目标：

每天复习代码随想录上的题目1-2道算法（时间充足可以继续）

今日碎碎念：

1）今天开始是二叉树系列

2）出租屋里不知道干啥，看看书啊刷刷算法，打打游戏，学学技术啥的，不让自己太闲着才行。

3）天天都是吃外卖，不出门了都，后续等到9号回来之后继续开始整理八股（以复习为主）。

---

力扣刷题

算法

力扣144：144. 二叉树的前序遍历

递归做法

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
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);}
}

迭代做法

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<Integer>();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;}
}

---

力扣94：94. 二叉树的中序遍历

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();inorder(root,res);return res;}void inorder(TreeNode root,List<Integer> res){if(root == null) return;inorder(root.left,res);res.add(root.val);inorder(root.right,res);}
}

迭代做法

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();if(root == null) return res;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();res.add(cur.val);//找右边cur = cur.right;}}return res;}
}

---

力扣145：145. 二叉树的后序遍历

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();postorder(root,res);return res;}void postorder(TreeNode root,List<Integer> res){if(root == null) return;postorder(root.left,res);postorder(root.right,res);res.add(root.val);}
}

迭代方法

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();if(root == null) return res;//用栈来做迭代Stack<TreeNode> stack = new Stack<>();stack.push(root);while(!stack.isEmpty()){TreeNode node = stack.pop();res.add(node.val);if(node.left!=null){stack.push(node.left);}if(node.right!=null){stack.push(node.right);}}//后序迭代我们不好实现，直接用前序遍历然后反转Collections.reverse(res);return res;}
}

---