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 ListInteger inorderTraversal(TreeNode root) { ListInteger result new ArrayList(); if (root null) { return result; } ListInteger left inorderTraversal(root.left); result.addAll(left); result.add(root.val); ListInteger 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 ListInteger inorderTraversal(TreeNode root) { ListInteger result new ArrayList(); if (root null) { return result; } DequeTreeNode 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; } }