【算法刷题day14】Leetcode:144.二叉树的前序遍历、94.二叉树的中序遍历、145.二叉树的后序遍历

草稿图网站
java的Deque

二叉树递归遍历

题目：
144.二叉树的前序遍历
94.二叉树的中序遍历
145.二叉树的后序遍历
解析：代码随想录解析

解题思路

递归遍历
前序：NLR
中序：LNR
后序：LRN

代码

/*** 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<Integer>();preorder(root, res);return res;}public void preorder(TreeNode root, List<Integer> res){if (root == null)return;res.add(root.val);preorder(root.left, res);preorder(root.right, res);}
}//中序
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();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> res = new ArrayList<Integer>();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);}
}

总结

暂无

二叉树的迭代遍历

题目：
144.二叉树的前序遍历
94.二叉树的中序遍历
145.二叉树的后序遍历
解析：代码随想录解析

解题思路

前序：利用一个栈，每次出栈并入栈。
中序：利用一个栈，cur指向root节点，一直走左子树并入栈到空；cur为空时输出栈顶的val，然后使cur指向出栈节点右子树，重复上述步骤。
后序：LRN反过来是NRL，也就是前序换一下，最后倒转一下。

代码

/*** 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<Integer>();if (root == null)return res;Stack<TreeNode> stack = new Stack<TreeNode>();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> res = new ArrayList<Integer>();if (root == null)return res;Stack<TreeNode> stack = new Stack<TreeNode>();TreeNode cur = root;while (!stack.isEmpty() || cur != null){if (cur != null){stack.push(cur);cur = cur.left;}else{cur = stack.pop();res.add(cur.val);cur = cur.right;}}return res;}
}//后序
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();if (root == null)return res;Stack<TreeNode> stack = new Stack<TreeNode>();stack.push(root);while(!stack.isEmpty()){TreeNode tmp = stack.pop();res.add(tmp.val);if (tmp.left != null)stack.push(tmp.left);if (tmp.right != null)stack.push(tmp.right);}Collections.reverse(res);return res;}
}

总结

死去的408记忆在攻击我

二叉树的统一迭代法

题目：
144.二叉树的前序遍历
94.二叉树的中序遍历
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> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();if (root == null)return res;Stack<TreeNode> stack = new Stack<TreeNode>();stack.push(root);while(!stack.isEmpty()){TreeNode node = stack.peek();if (node != null){stack.pop();if (node.right != null) stack.push(node.right);if (node.left != null)  stack.push(node.left);stack.push(node);stack.push(null);    }else{stack.pop();node = stack.pop();res.add(node.val);}}return res;}
}//中序
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();if (root == null)return res;Stack<TreeNode> stack = new Stack<TreeNode>();stack.push(root);while(!stack.isEmpty()){TreeNode node = stack.peek();if (node != null){stack.pop();if (node.right != null) stack.push(node.right);stack.push(node);stack.push(null); if (node.left != null)  stack.push(node.left);}else{stack.pop();node = stack.pop();res.add(node.val);}}return res;}
}//后序
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();if (root == null)return res;Stack<TreeNode> stack = new Stack<TreeNode>();stack.push(root);while(!stack.isEmpty()){TreeNode node = stack.peek();if (node != null){stack.pop();stack.push(node);stack.push(null); if (node.right != null) stack.push(node.right);if (node.left != null)  stack.push(node.left);}else{stack.pop();node = stack.pop();res.add(node.val);}}return res;}
}

总结

感觉记住了，感觉。