LeetCode94. 二叉树的中序遍历（java,python,递归,迭代）

本文主要是介绍LeetCode94. 二叉树的中序遍历（java,python,递归,迭代），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题目

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

示例:

输入: [1,null,2,3]

   1\2/3

输出: [1,3,2]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解答

方法一：迭代

Java 实现：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
/*(left, in, right)*/
class Solution {public List<Integer> inorderTraversal(TreeNode root) {ArrayList<Integer> res = new ArrayList<>();if (root == null)return res;/*链表*/LinkedList<TreeNode> stack = new LinkedList();TreeNode node = root;while(node != null || !stack.isEmpty()){while(node != null){stack.push(node);node = node.left;}node = stack.pop();res.add(node.val);node = node.right;}return res;}
}

python实现迭代：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution:def inorderTraversal(self, root: TreeNode) -> List[int]:# 迭代stack = []res = []while root or stack:while root:stack.append(root)root = root.leftroot = stack.pop()res.append(root.val)root = root.rightreturn res

方法二：递归
Java实现递归：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution 
{public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res=new ArrayList<>();if(root==null){return res;}inorder(root, res);return res;}public void inorder(TreeNode root, List<Integer> res) {if(root.left!=null){inorder(root.left, res);}res.add(root.val);if(root.right!=null){inorder(root.right, res);}}
}

python实现递归：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution:def inorderTraversal(self, root: TreeNode) -> List[int]:# 递归res = []self.inOrder(root,res)return resdef inOrder(self, root, res):if root:self.inOrder(root.left,res)res.append(root.val)self.inOrder(root.right,res)