首页 > 试题广场 >

二叉树的中序遍历

[编程题]二叉树的中序遍历

热度指数：87369 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

数据范围：树上节点数满足 $0 \le n \le 1000$ ，树上每个节点的值满足 $-1000 \le val \le 1000$
进阶：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

示例1

输入

{1,2,#,#,3}

输出

[2,3,1]

说明

示例2

输入

{}

输出

[]

示例3

输入

{1,2}

输出

[2,1]

说明

示例4

输入

{1,#,2}

输出

[1,2]

说明

备注:

树中节点数目在范围 [0, 100] 内
树中的节点的值在[-100,100]以内

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Aniki_

非递归不用堆栈的中序遍历 Moris

using System;

using System.Collections.Generic;

/*
public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode (int x)
    {
        val = x;
    }
}
*/

class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型一维数组
*/
public List<int> inorderTraversal (TreeNode root) {
// write code here
List<int> list = new List<int>();
if(root == null) return list;
//1非递归不用堆栈的中序遍历
//思想如下：1、如果当前左孩子为空，直接输出当前结点，
// 2、否则找左孩子的右孩子结点，直到结点为空或者等于当前结点
// 3、结点为空时，结点的右孩子设置为当前结点，当前结点移到左孩子结点
// 4、结点不为空时，输出当前结点，同时取消结点的右孩子结点，当前结点挪到当前结点的右孩子
TreeNode cur = root;
TreeNode next = null;
while(cur!=null)
{
if(cur.left==null)
{
list.Add(cur.val);
cur = cur.right;//right一定不为空，为空的只有最后一个结点
}
else
{
next = cur.left;
while(next.right!=null && next.right != cur)
{
next = next.right;
}
if(next.right == null)
{
next.right = cur;
cur = cur.left;
}
else
{
list.Add(cur.val);
next.right = null;
cur = cur.right;
}
}
}
// 2递归用法 D(root,list);
//3非递归写法，使用堆栈
// Stack<TreeNode> s = new Stack<TreeNode>();
// s.Push(root);
// TreeNode cur = root.left;
// while(s.Count!=0 || cur!=null)
// {
// while(cur != null)
// {
// s.Push(cur);
// cur = cur.left;
// }
// cur = s.Pop();
// list.Add(cur.val);
// cur = cur.right;
// }
return list;
}

public void D(TreeNode node, List<int> list)
{
if(node == null) return;
D(node.left,list);
list.Add(node.val);
D(node.right,list);
}
}

发表于 2022-04-02 13:20:47 回复(0)

C++

pein531

Morris遍历，时间复杂度O(N)，空间复杂度O(1)

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
    vector<int> inorderTraversal(TreeNode* root) {
        // write code here
        vector<int> inOrderSeq;
        if(root == nullptr) return inOrderSeq;
        TreeNode* cur = root;
        TreeNode* mostRight = nullptr;
        while(cur != nullptr){
            mostRight = cur->left;
            if(mostRight != nullptr){
                while(mostRight->right != nullptr && mostRight->right != cur) mostRight = mostRight->right;
                if(mostRight->right == nullptr){
                    mostRight->right = cur;
                    cur = cur->left;
                    continue;
                }else{
                    // 会到达两次的节点在第二次到达时追加
                    inOrderSeq.push_back(cur->val);
                    mostRight->right = nullptr;
                }
            }else{
                // 只会到达一次的节点直接追加
                inOrderSeq.push_back(cur->val);
            }
            cur = cur->right;
        }
        return inOrderSeq;
    }
};

发表于 2021-11-21 11:36:30 回复(0)

岛。201904182324772

public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型一维数组
*/
public int[] inorderTraversal (TreeNode root) {
ArrayList<Integer> res=new ArrayList<>();
inorder(root,res);
int i=0;
int result[] = new int[res.size()];
for(int a:res){
result[i++]=a;
}
return result;
// write code here
}
public void inorder(TreeNode root,ArrayList<Integer> res){
if(root==null) return;
inorder(root.left,res);
res.add(root.val);
inorder(root.right,res);
}
}

发表于 2021-09-07 20:29:53 回复(0)

Java

牛客421289926号

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型一维数组
     */
    public int[] inorderTraversal (TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> s = new Stack<>();
        if (root == null){
            return new int[0];
        }
        TreeNode current = root;
        while (!s.empty()||current!=null){
            while(current!=null){
                s.push(current);
                current = current.left;
            }
            if (!s.empty()){
                TreeNode tree = s.pop();
                list.add(tree.val);
                current = tree.right;
            }
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
    
}

发表于 2021-04-13 10:08:47 回复(0)

Chromium丶

static int count = 0;
void inOrder(struct TreeNode* root,int *a){
    if(root != NULL){
        inOrder(root->left, a);
        a[count++] = root->val;
        inOrder(root->right, a);
    }
}

int* inorderTraversal(struct TreeNode* root, int* returnSize ) {
    int *a = (int*)malloc(sizeof(int)*1001);
    inOrder(root, a);
    *returnSize = count;
    return a;
    // write code here
}

发表于 2022-03-17 16:18:13 回复(0)

Python 3

秋招小拉吉

你们都不会超时吗，为什么我python用中序遍历的递归模板第11个测试案例超时

发表于 2022-03-01 14:13:06 回复(5)

Java

牛客839384289号

    ArrayList<Integer> inList = new ArrayList<>();
    
    public int[] inorderTraversal (TreeNode root) {
        // write code here
        inOrder(root);
        return inList.stream().mapToInt(Integer::valueOf).toArray();
    }
    
    public void inOrder(TreeNode root){
        if(root==null){
            return;
        }
        inOrder(root.left);
        inList.add(root.val);
        inOrder(root.right);
    }

发表于 2022-05-14 13:33:11 回复(0)

C++

牛娃牛娃

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
    vector<int> res;
    vector<int> inorderTraversal(TreeNode* root) {
        if(root==nullptr)return res;
        inorderTraversal(root->left);
        res.push_back(root->val);
        inorderTraversal(root->right);
        return res;
    }
};

发表于 2022-04-27 18:00:29 回复(0)

Python 3

lun__

import sys
sys.setrecursionlimit(100000) #例如这里设置为一百万

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

发表于 2022-07-03 16:59:41 回复(0)

cqu后起之秀

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
    vector<int> inorderTraversal(TreeNode* root) {
        
        // write code here
        vector<int> res;
        inorderTraversal(res,root);
        return res;
    }
    
    void inorderTraversal(vector<int> &res,TreeNode* root){
        if(NULL==root) return;
        inorderTraversal(res,root->left);
        res.push_back(root->val);
        inorderTraversal(res,root->right);
    }
};

发表于 2021-07-05 15:25:14 回复(0)

Rust

clever-kalamh7o

struct Solution{

}

impl Solution {
    fn new() -> Self {
        Solution{}
    }

    pub fn inorderTraversal(&self, root: Option<Box<TreeNode>>) -> Vec<i32> {
        // write code here
        let mut res = vec![];

        fn dfs(node: &Option<Box<TreeNode>>, arr: &mut Vec<i32>) {
            if let Some(ref node) = *node {
                dfs(&node.left, arr);
                arr.push(node.val);
                dfs(&node.right, arr);
            }
        }

        dfs(&root, &mut res);
        res
    }
}

发表于 2024-03-06 12:22:56 回复(0)

你一定会有offer

public class Solution {
    /**
     *	不断遍历左节点，同时压入栈，当没有左节点的时候证明到底了，可以将栈顶元素弹出放入集合
	 *	然后判断弹出元素的右节点，方法都是一样，不断循环这个过程，就可以完成中序遍历
     *	注意结束条件是当前节点和队列都为空时
     * 
     * @param root TreeNode类 
     * @return int整型一维数组
     */
    public int[] inorderTraversal (TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        ArrayList<Integer> list = new ArrayList<>();
        TreeNode curr = root;
        while(curr != null || !stack.isEmpty()){
            if(curr != null){
                stack.push(curr);
                curr = curr.left;
            }else{
                TreeNode pop = stack.pop();
                list.add(pop.val);
                curr = pop.right;
            }
        }
        int[] arr = new int[list.size()];
        for(int i = 0; i < list.size(); i++){
            arr[i] = list.get(i);
        }
        return arr;
    }
}

发表于 2023-08-10 20:40:29 回复(0)

JavaScript Node

牛客931461884号

let arr=[]
function inorderTraversal( root ) {
    // write code here
    if(root==null) return [];
    if(root){
        inorderTraversal(root.left);
        arr.push(root.val);
        inorderTraversal(root.right);
    }
  return arr;  
}

发表于 2023-04-01 20:34:23 回复(0)

BlueProtocol

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型一维数组
     */
    public ArrayList<Integer> list = new ArrayList<Integer>();

    public void get(TreeNode root) {
        if (root == null) {
            return ;
        }
        get(root.left);
        list.add(root.val);
        get(root.right);
    }

    public int[] inorderTraversal (TreeNode root) {
        // write code here
        get(root);
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}

发表于 2023-03-05 17:00:15 回复(0)

zipman

morris中序 O(1)空间复杂度

func inorderTraversal(root *TreeNode) []int {
	res := make([]int, 0)
	cur, mostRight := root, &TreeNode{}
	for cur != nil {
		mostRight = cur.Left
		if mostRight != nil {
			for mostRight.Right != nil && mostRight.Right != cur {
				mostRight = mostRight.Right
			}
			if mostRight.Right != cur {
				mostRight.Right = cur
				cur = cur.Left
				continue
			} else {
				mostRight.Right = nil
			}
		}
		res = append(res, cur.Val)
		cur = cur.Right
	}
	return res
}

发表于 2023-01-12 18:33:48 回复(0)

Java

键盘都敲坏了.

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型一维数组
     */
    public int[] inorderTraversal (TreeNode root) {
        if(root == null){ return new int[0]; }

        // 中序遍历: left -> this -> right

        // 存储中序遍历的结果
        List<Integer> arrayList = new ArrayList();
        // 中序遍历
        inDFS(root, arrayList);
        // 转int数组
        return arrayList.stream().mapToInt(i->i).toArray();

    }
    public void inDFS (TreeNode root, List<Integer> arrayList) {
        // 节点空，返回
        if(root == null){
            return;
        }
        
        // 向左遍历
        inDFS (root.left, arrayList);
        // 存储当前节点
        arrayList.add(root.val);
        // 向右遍历
        inDFS (root.right, arrayList);
    }
}

发表于 2022-11-01 13:50:15 回复(0)

C++

Spectre_

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
    vector<int> inorderTraversal(TreeNode* root) {
        // 时间复杂度O(N)，空间复杂度O(N)
        vector<int> res;
        stack<TreeNode*> stk;
        TreeNode* node = root;
        while (!stk.empty() || node) {
            while (node) {
                stk.push(node);
                node = node->left;
            }
            node = stk.top();
            stk.pop();
            res.push_back(node->val);
            node = node->right;
        }
        return res;
    }
};

发表于 2022-10-09 10:45:02 回复(0)

tach1koma

迭代版

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode *> s;
        TreeNode *curr = root;
        while (curr) {
            while (curr) {
                s.push(curr);
                curr = curr->left;
            }
            while (!s.empty()) {
                curr = s.top();
                s.pop();
                ans.push_back(curr->val);
                if (curr->right)
                    break;
            }
            if (curr->right)
                curr = curr->right;
            else
                break;
        }
        return ans;
    }
};

发表于 2022-01-15 13:05:11 回复(0)

xxxmiracle

#include <assert.h>

static int count = 0;

void inOrder(struct TreeNode* root, int* a) {

if (root == NULL) {

return;

}

if (root->left != NULL) {

inOrder(root->left, a);

a[count++] = root->val;

inOrder(root->right, a);

} else {

a[count++] = root->val;

inOrder(root->right, a);

}

int* inorderTraversal(struct TreeNode* root, int* returnSize ) {

// write code here

int* a = (int*)malloc(sizeof(int) * 1001);

inOrder(root, a);

*returnSize = count;

return a;

}

发表于 2024-04-14 16:23:55 回复(0)

JavaScript Node

陈彬杰a

function inorderTraversal( root ) {
    if (!root) return [];
    return [...inorderTraversal(root.left), root.val, ...inorderTraversal(root.right)]
}

编辑于 2024-04-08 15:21:43 回复(0)

提交观点

问题信息

树 dfs 递归广度优先搜索(BFS)

难度：

137条回答 251收藏 4754浏览

通过挑战的用户

查看代码

最後的輕語

2023-01-09 10:43:15
小苏是懒狗

2022-10-10 10:15:20
牛客31027...

2022-09-16 17:03:16
牛客70131...

2022-09-16 16:21:22
snailCl...

2022-09-16 16:07:13

二叉树的中序遍历

输入

输出

说明

输入

输出

输入

输出

说明

输入

输出

说明

备注:

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题