首页 > 试题广场 >

二叉树的中序遍历

[编程题]二叉树的中序遍历
  • 热度指数：112321 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个二叉树的根节点root，返回它的中序遍历结果。

数据范围：树上节点数满足 ，树上每个节点的值满足 -1000 \le val \le 1000
进阶：空间复杂度 ，时间复杂度
示例1

输入

{1,2,#,#,3}

输出

[2,3,1]

说明
示例2

输入

{}

输出

[]
示例3

输入

{1,2}

输出

[2,1]

说明
示例4

输入

{1,#,2}

输出

[1,2]

说明

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

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
C#
Aniki_头像 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头像 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头像 岛。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)
C
Chromium丶头像 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号头像 牛客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__头像 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后起之秀头像 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)
Java
牛客421289926号头像 牛客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)
C
StellarVibes头像 StellarVibes
void fuc(struct TreeNode* root, int* arr,int * count)
{
    if (root == NULL)
    {
        return;
    }
    fuc(root->left, arr,count);
    arr[*count] = root->val;
    //printf("%d ",arr[*count]);
    //printf("%d\n",*count);
    (*count)++;
    fuc(root->right, arr,count);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize ) {
    int* arr = (int*)malloc(sizeof(4)*1000);
    int count = 0;
    fuc(root, arr,&count);
    //while(*arr)
    //{
        //printf("%d ",*arr);
        //arr++;
    //}
    *returnSize=count;
    return arr;
}
发表于 2024-12-14 18:19:58 回复(1)
JavaScript Node
陈彬杰a头像 陈彬杰a 
function inorderTraversal( root ) {
    if (!root) return [];
    return [...inorderTraversal(root.left), root.val, ...inorderTraversal(root.right)]
}


编辑于 2024-04-08 15:21:43 回复(0)
C
一个优雅的程序猿头像 一个优雅的程序猿 
void inorderTraver(struct TreeNode* root, int* res, int* StaticReturnSize ) {
    if(root->left!=NULL) 
        inorderTraver(root->left, res, StaticReturnSize);
    res[(*StaticReturnSize)++] = root->val;
    if(root->right!=NULL) 
        inorderTraver(root->right, res, StaticReturnSize);
}    
int* inorderTraversal(struct TreeNode* root, int* returnSize ) {
    static int res[1000]={0}, StaticReturnSize=0;
    if(root==NULL) 
        return NULL;
    inorderTraver(root, res, &StaticReturnSize);
    *returnSize = StaticReturnSize;
    return res;
}

编辑于 2024-03-16 15:59:23 回复(0)
Rust
clever-kalamh7o头像 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)
C++
牛客706368877号头像 牛客706368877号
递归效率太低 
/**
 * 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
        stack<TreeNode*> st;
        vector<int> vec;
        TreeNode *node = root;
        while (node != nullptr) {
            st.push(node);
            node = node->left;
        }

        while (!st.empty()) {
            node = st.top();
            st.pop();
            vec.push_back(node->val);
            node = node->right;
            while (node != nullptr) {
                st.push(node);
                node = node->left;
            }
        }

        return vec;
    }
};


发表于 2023-09-16 15:37:18 回复(0)
你一定会有offer头像 你一定会有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号头像 牛客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头像 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头像 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)
提交观点

问题信息

树 dfs 递归 广度优先搜索(BFS)
难度：
159条回答 9710浏览

热门推荐

通过挑战的用户

查看代码

相关试题

二叉树的中序遍历

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号