JAVA练习304- 二叉树的中序遍历

题目概览

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

进阶:递归算法很简单，你可以通过迭代算法完成吗？

来源：94. 二叉树的中序遍历 - 力扣（LeetCode）

解题分析

方法一：递归

左 - 根 - 右 顺序递归即可。

时间复杂度：O(n)
空间复杂度：O(n)

/** * 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> result = new ArrayList<>(); if (root == null) { return result; } List<Integer> left = inorderTraversal(root.left); result.addAll(left); result.add(root.val); List<Integer> right = inorderTraversal(root.right); result.addAll(right); return result; } }

方法二：迭代 + 栈

根据栈先进后出的特性，可以现将二叉树的所有左节点都入栈，栈顶的节点一定是第一个节点，出栈并记录该节点值，将该节点右节点继续刚才左节点入栈的操作，没有则继续出栈，直到栈为空。

时间复杂度：O(n)
空间复杂度：O(n)

/** * 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> result = new ArrayList<>(); if (root == null) { return result; } Deque<TreeNode> stack = new LinkedList<>(); while(root != null || !stack.isEmpty()) { while(root != null) { stack.push(root); root = root.left; } TreeNode node = stack.pop(); result.add(node.val); root = node.right; } return result; } }