94.二叉树的中序遍历

链接：94.二叉树的中序遍历
难度：Easy
标签：栈、树、深度优先搜索、二叉树
简介：给定一个二叉树，返回它的中序 遍历。

题解 1 - java

• 编辑时间：2020-02-21
• 内存消耗：38MB
• 编程语言：java
• 解法介绍：递归。

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
    	LinkedList<Integer> list = new LinkedList<Integer>();
        if(root==null)return list;
        inorder(list,root);
        return list;
    }
    public void inorder(List<Integer> list,TreeNode node) {
    	if(node.left!=null)inorder(list, node.left);
    	list.add(node.val);
    	if(node.right!=null)inorder(list, node.right);
    }
}

题解 2 - java

• 编辑时间：2020-02-21
• 执行用时：1ms
• 内存消耗：37.8MB
• 编程语言：java
• 解法介绍：迭代。

public List<Integer> inorderTraversal(TreeNode root) {
	List<Integer> list = new LinkedList<Integer>();
	if(root==null) return list;
	Stack<TreeNode> stack= new Stack<TreeNode>();
	TreeNode node = root;
	while(!stack.isEmpty()||node!=null) {
		while(node!=null) {
			stack.push(node);
			node=node.left;
		}
		node=stack.pop();
		list.add(node.val);
		node=node.right;
	}
	return list;
}

题解 3 - typescript

• 编辑时间：2020-09-14
• 执行用时：72ms
• 内存消耗：37.5MB
• 编程语言：typescript
• 解法介绍：递归。

function inorderTraversal(root: TreeNode | null): number[] {
  const ans: number[] = [];
  _inorder(root);
  return ans;
  function _inorder(node: TreeNode | null): void {
    if (node === null) return;
    node.left !== null && _inorder(node.left);
    ans.push(node.val);
    node.right !== null && _inorder(node.right);
  }
}

题解 4 - typescript

• 编辑时间：2020-09-14
• 执行用时：84ms
• 内存消耗：37.5MB
• 编程语言：typescript
• 解法介绍：迭代。

function inorderTraversal(root: TreeNode | null): number[] {
  if (root === null) return [];
  const ans: number[] = [];
  const stack: TreeNode[] = [root];
  const used = new Set<TreeNode>();
  while (stack.length !== 0) {
    const node = stack.pop() as TreeNode;
    if (used.has(node)) {
      ans.push(node.val);
    } else {
      used.add(node);
      node.right && stack.push(node.right);
      stack.push(node);
      node.left && stack.push(node.left);
    }
  }
  return ans;
}

题解 5 - c

• 编辑时间：2021-11-27
• 内存消耗：5.6MB
• 编程语言：c
• 解法介绍：递归。

// 先递归左，再计算当前节点，再递归右
void order(struct TreeNode *root, int *arr, int *idx){
    if (!root) return ;
    order(root->left, arr, idx);
    arr[(*idx)++] = root->val;
    order(root->right, arr, idx);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize){
    int *arr = (int *)malloc(sizeof(int) * 100);
    *returnSize = 0;
    order(root, arr, returnSize);
    return arr;
}

题解 6 - python

• 编辑时间：2024-02-10
• 执行用时：38ms
• 内存消耗：16.41MB
• 编程语言：python
• 解法介绍：dfs。

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        arr = []
        def dfs(node: Optional[TreeNode]):
            if not node: return
            dfs(node.left)
            arr.append(node.val)
            dfs(node.right)
        dfs(root)
        return arr