二叉树的前序中序后续遍历
144.二叉树的前序遍历(opens new window)
145.二叉树的后序遍历(opens new window)
解题思路：
二叉树的前序、中序和后序遍历是常见的树遍历方式。下面我将详细解释每种遍历方式的思路和实现方法：
- 前序遍历（Preorder Traversal）：
- 遍历顺序：根节点 -> 左子树 -> 右子树。
- 实现思路：
- 如果树为空，则返回。
- 首先访问根节点，然后递归地对左子树进行前序遍历。
- 最后递归地对右子树进行前序遍历。
- 中序遍历（Inorder Traversal）：
- 遍历顺序：左子树 -> 根节点 -> 右子树。
- 实现思路：
- 如果树为空，则返回。
- 首先递归地对左子树进行中序遍历。
- 然后访问根节点。
- 最后递归地对右子树进行中序遍历。
- 后序遍历（Postorder Traversal）：
- 遍历顺序：左子树 -> 右子树 -> 根节点。
- 实现思路：
- 如果树为空，则返回。
- 首先递归地对左子树进行后序遍历。
- 然后递归地对右子树进行后序遍历。
- 最后访问根节点。
让我们通过一个简单的二叉树来演示前序、中序和后序遍历的过程。
考虑以下二叉树：
1
/ \
2 3
/ \ / \
4 5 6 7
- 前序遍历（Preorder Traversal）：根节点 -> 左子树 -> 右子树
- 遍历顺序：1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7
- 步骤：
- 首先访问根节点 1。
- 然后递归地对左子树进行前序遍历，访问节点 2，再递归地对左子树进行前序遍历，访问节点 4。
- 左子树为空时，回溯到节点 2，递归地对右子树进行前序遍历，访问节点 5。
- 回溯到根节点 1，递归地对右子树进行前序遍历，访问节点 3，再递归地对左子树进行前序遍历，访问节点 6。
- 左子树为空时，回溯到节点 3，递归地对右子树进行前序遍历，访问节点 7。
- 遍历结果：[1, 2, 4, 5, 3, 6, 7]
- 中序遍历（Inorder Traversal）：左子树 -> 根节点 -> 右子树
- 遍历顺序：4 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7
- 步骤：
- 首先递归地对左子树进行中序遍历，访问节点 4。
- 回溯到节点 2，访问节点 2。
- 然后递归地对右子树进行中序遍历，访问节点 5。
- 回溯到根节点 1，访问节点 1。
- 递归地对左子树进行中序遍历，访问节点 6。
- 回溯到节点 3，访问节点 3。
- 最后递归地对右子树进行中序遍历，访问节点 7。
- 遍历结果：[4, 2, 5, 1, 6, 3, 7]
- 后序遍历（Postorder Traversal）：左子树 -> 右子树 -> 根节点
- 遍历顺序：4 -> 5 -> 2 -> 6 -> 7 -> 3 -> 1
- 步骤：
- 首先递归地对左子树进行后序遍历，访问节点 4。
- 回溯到节点 2，递归地对右子树进行后序遍历，访问节点 5。
- 回溯到根节点 1，访问节点 1。
- 递归地对左子树进行后序遍历，访问节点 6。
- 回溯到节点 3，递归地对右子树进行后序遍历，访问节点 7。
- 遍历结果：[4, 5, 2, 6, 7, 3, 1]
代码实现：
递归方式：
递归前序遍历：
/**
* 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 {
List<Integer> res = new ArrayList();
public List<Integer> preorderTraversal(TreeNode root) {
dfs(root);
return res;
}
public void dfs(TreeNode root){
if(root == null){
return;
}
res.add(root.val);
dfs(root.left);
dfs(root.right);
}
}
递归中序遍历：
/**
* 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 {
List<Integer> res = new ArrayList();
public List<Integer> inorderTraversal(TreeNode root) {
dfs(root);
return res;
}
public void dfs(TreeNode root){
if(root == null){
return;
}
dfs(root.left);
res.add(root.val);
dfs(root.right);
}
}
递归后续遍历：
/**
* 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 {
List<Integer> res = new ArrayList();
public List<Integer> postorderTraversal(TreeNode root) {
dfs(root);
return res;
}
public void dfs(TreeNode root){
if(root == null){
return;
}
dfs(root.left);
dfs(root.right);
res.add(root.val);
}
}
非递归方式：
实现先序中序后序遍历
当然！下面我将使用Java来再次讲解如何实现二叉树的非递归先序、中序和后序遍历。
首先，我们定义二叉树的节点类（假设节点的值为整数）：
class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
非递归先序遍历：
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class PreorderTraversal {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
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;
}
}
非递归中序遍历：
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class InorderTraversal {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
result.add(curr.val);
curr = curr.right;
}
return result;
}
}
非递归后序遍历：
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class PostorderTraversal {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Stack<TreeNode> stack = new Stack<>();
Stack<Integer> output = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
output.push(node.val);
if (node.left != null) {
stack.push(node.left);
}
if (node.right != null) {
stack.push(node.right);
}
}
while (!output.isEmpty()) {
result.add(output.pop());
}
return result;
}
}
评论区