当前位置：首页 > news >正文

算法：94. 二叉树的中序遍历--扩展前中后层序遍历

news 来源：原创 2024/7/7 17:19:54

中序遍历

给定一个二叉树的根节点 root ，返回 它的中序遍历 。

中遍历结果为：H D I B E J A F K C G

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

方法一：递归

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> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();Deque<TreeNode> stk = new LinkedList<TreeNode>();while (root != null || !stk.isEmpty()) {while (root != null) {stk.push(root);root = root.left;}root = stk.pop();res.add(root.val);root = root.right;}return res;}
}

前序遍历

先序遍历结果为：A B D H I E J C F K G

import java.util.Stack;// 定义二叉树节点
class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val = val;}
}public class PreorderTraversal {public static void preorderTraversal(TreeNode root) {if (root == null) {return;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode current = stack.pop();System.out.print(current.val + " ");// 先将右子树入栈，再将左子树入栈，这样出栈的顺序就是先左后右if (current.right != null) {stack.push(current.right);}if (current.left != null) {stack.push(current.left);}}}public static void main(String[] args) {// 创建二叉树TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.right = new TreeNode(3);root.left.left = new TreeNode(4);root.left.right = new TreeNode(5);// 非递归前序遍历System.out.println("非递归前序遍历结果：");preorderTraversal(root);}
}

后序遍历

后序遍历结果：H I D J E B K F G C A
在这里插入图片描述

import java.util.Stack;// 定义二叉树节点
class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val = val;}
}public class PostorderTraversal {public static void postorderTraversal(TreeNode root) {if (root == null) {return;}Stack<TreeNode> stack = new Stack<>();Stack<TreeNode> output = new Stack<>(); // 用于保存后序遍历结果stack.push(root);while (!stack.isEmpty()) {TreeNode current = stack.pop();output.push(current);if (current.left != null) {stack.push(current.left);}if (current.right != null) {stack.push(current.right);}}// 输出后序遍历结果while (!output.isEmpty()) {TreeNode node = output.pop();System.out.print(node.val + " ");}}public static void main(String[] args) {// 创建二叉树TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.right = new TreeNode(3);root.left.left = new TreeNode(4);root.left.right = new TreeNode(5);// 非递归后序遍历System.out.println("非递归后序遍历结果：");postorderTraversal(root);//非递归后序遍历结果：
//4 5 2 3 1}
}