代码随想录三刷day17

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

—二叉树的前中后序遍历，使用递归个迭代两种方法

一、力扣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> res = new ArrayList<>();fun(res,root);return res;}public void fun(List<Integer> list, TreeNode root){if(root == null){return ;}list.add(root.val);fun(list,root.left);fun(list,root.right);}
}

二、力扣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<>();fun(res,root);return res;}public void fun(List<Integer> res,TreeNode root){if(root == null){return;}fun(res,root.left);fun(res,root.right);res.add(root.val);}
}

三、力扣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<>();fun(res,root);return res;}public void fun(List<Integer> res , TreeNode root){if(root == null){return;}fun(res,root.left);res.add(root.val);fun(res,root.right);}
}

四、力扣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) {Deque<TreeNode> deq = new LinkedList<>();List<Integer> res = new ArrayList<>();if(root == null){return res;}deq.offerLast(root);while(!deq.isEmpty()){TreeNode p = deq.pollLast();res.add(p.val);if(p.right != null){deq.offerLast(p.right);}if(p.left != null){deq.offerLast(p.left);}}return res;}
}

无、力扣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) {Deque<TreeNode> deq = new LinkedList<>();List<Integer> res = new LinkedList<>();if(root == null){return res;}deq.offerLast(root);while(!deq.isEmpty()){TreeNode p = deq.pollLast();res.add(p.val);if(p.left != null){deq.offerLast(p.left);}if(p.right != null){deq.offerLast(p.right);}}Collections.reverse(res);return res;}
}

六、力扣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) {Deque<TreeNode> deq = new LinkedList();List<Integer> res = new LinkedList<>();if(root == null){return res;}TreeNode p = root;while(!deq.isEmpty() || p != null){if(p != null){deq.offerLast(p);p = p.left;}else{p = deq.pollLast();res.add(p.val);p = p.right;}}return res;}
}