首页 > 试题广场 >

二叉树的中序遍历

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

热度指数：105290 时间限制：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，点此查看相关信息

算法知识视频讲解

Java

17c89

import java.util.*;

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

/**
 * NC161 二叉树的中序遍历
 * @author d3y1
 */
public class Solution {
    private ArrayList<Integer> list = new ArrayList<>();

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

    /**
     * 递归
     * @param root
     * @return
     */
    private int[] solution1(TreeNode root){
        inOrder(root);

        int[] results = new int[list.size()];
        for(int i=0; i<list.size(); i++){
            results[i] = list.get(i);
        }

        return results;
    }

    /**
     * 中序遍历(dfs)
     * @param root
     */
    private void inOrder(TreeNode root){
        if(root == null){
            return;
        }

        inOrder(root.left);
        list.add(root.val);
        inOrder(root.right);
    }

    /**
     * 迭代(栈)
     * @param root
     * @return
     */
    private int[] solution2(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();

        TreeNode curr;
        while(root!=null || !stack.isEmpty()){
            // 最左边
            while(root != null){
                stack.push(root);
                root = root.left;
            }

            curr = stack.pop();
            list.add(curr.val);

            root = curr.right;
        }

        int[] results = new int[list.size()];
        for(int i=0; i<list.size(); i++){
            results[i] = list.get(i);
        }

        return results;
    }
}

发表于 2025-01-13 12:11:41 回复(0)

Java

牛客348570162号

public int[] inorderTraversal (TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        traversal(list,root);
        int[] r = new int[list.size()];
        for(int i=0;i<list.size();i++){
            r[i] = list.get(i);
        }
        return r;
    }

    public void traversal (ArrayList<Integer> list,TreeNode node) {
        if(node == null) return;
        if(node.left != null) traversal(list,node.left);
        list.add(node.val);
        if(node.right != null) traversal(list,node.right);
    }

发表于 2024-08-26 15:27:51 回复(0)

Java

人间水长东

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) {
        // write code here

        // 1.初始化一个ArrayList用于动态添加数据
        ArrayList<Integer> resultList = new ArrayList<>();

        // 2.调用中序遍历递归函数
        process(resultList, root);

        // 3.将ArrayList转换成int[]并返回
        return listToArray(resultList);
    }

    // 中序遍历递归函数
    public void process(ArrayList<Integer> resultList, TreeNode root) {
        if (root == null) {
            return;
        }
        process(resultList, root.left);
        resultList.add(root.val);
        process(resultList, root.right);
    }

    // ArrayList转int[]
    public int[] listToArray(ArrayList<Integer> resultList) {
        int[] resultArray = new int[resultList.size()];
        for (int i = 0; i < resultArray.length; i++) {
            resultArray[i] = resultList.get(i);
        }
        return resultArray;
    }
}

发表于 2024-07-29 19:01:07 回复(0)

Java

Naaaaaaaaaaasus

家人们, {1, 2, 3, #, #, 4} 这种输入是什么含义啊？能画张图吗？# 代表什么？

如果再复杂一点, {1,2,3,4,6,9} 这个二叉树长啥样？

发表于 2024-01-31 09:36:35 回复(0)

Java

Frank.HUANG

困难题我唯唯诺诺，简单题我重拳出击！

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 {
    public int[] inorderTraversal (TreeNode root) {
        // write code here
        if(root==null){
            return new int[0];
        }

        List<Integer> ans=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        while(root!=null || !stack.isEmpty()){
            while(root!=null){
                stack.push(root);
                root=root.left;
            }

            TreeNode node=stack.pop();
            ans.add(node.val);
            root=node.right;
        }

        return ans.stream().mapToInt(Integer::intValue).toArray();
    }
}

发表于 2023-11-22 22:00:06 回复(0)

Java

李克雷

public class Solution {
    /**
     * 给定一个二叉树的根节点root，返回它的中序遍历结果。
     *
     *
     * @param root TreeNode类
     * @return int整型一维数组
     */
    public int[] inorderTraversal (TreeNode root) {
        // write code here
        if (null == root) {
            return new int[] {};
        }
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> nums = new ArrayList<>();
        pushAllLeft(root, stack);
        while (!stack.isEmpty()) {
            TreeNode top = stack.pop();
            nums.add(top.val);
            //如果出栈的节点是非叶子节点，将其标记为root节点，并将将root节点及其孩子的左节点加入
            if (top.right != null) {
                root = top.right;
                pushAllLeft(root, stack);
            }
        }
        return list2Array(nums);
    }

    /**
     * 将root节点及其孩子的左节点加入栈
     *
     *
     * @param root TreeNode类
     * @param stack Stack<TreeNode>
     * @return int整型一维数组
     */
    public void pushAllLeft(TreeNode root, Stack<TreeNode> stack) {
        TreeNode curr = root;
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
    }

    /**
     *  List<Integer>转化为int[]
     *
     *
     * @param nums List<Integer>类
     * @return int整型一维数组
     */
    public int[] list2Array(List<Integer> nums) {
        int[] numArray = new int[nums.size()];
        for (int i = 0; i < nums.size(); i++) {
            numArray[i] = nums.get(i);
        }
        return numArray;
    }

}

发表于 2023-10-12 12:09:22 回复(0)

Java

七号公园的街灯

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

发表于 2023-08-18 10:56:29 回复(0)

Java

DDwu

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整型一维数组
     */
    List<Integer> list = new ArrayList<>();
    public int[] inorderTraversal (TreeNode root) {
        if (root != null) {
            inorderTraversal(root.left);
            list.add(root.val);
            inorderTraversal(root.right);
        }
        int[] res=new int[list.size()];
        for(int i =0;i<list.size();i++){
            res[i]=list.get(i);
        }
        return res;
    }

    // public int[] inorderTraversal (TreeNode root) {
    //     // write code here
    //     List<Integer> list=new ArrayList<>();
    //     Stack<TreeNode> stack=new Stack<>();
    //     if(root==null){
    //         return new int[0];
    //     }
    //     TreeNode cur=root;
    //     while(!stack.isEmpty()||cur!=null){
    //         while(cur!=null){
    //             stack.push(cur);
    //             cur=cur.left;
    //         }
    //         if(!stack.isEmpty()){
    //             TreeNode temp=stack.pop();
    //             list.add(temp.val) ;
    //             cur=temp.right;
    //         }
    //     }
    //     int[] res=new int[list.size()];
    //     for(int i =0;i<list.size();i++){
    //         res[i]=list.get(i);
    //     }
    //     return res;
    // }
}

发表于 2023-07-21 22:54:27 回复(0)

Java

一块大奶酪呀

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型一维数组
     */
     public List<Integer> list=new ArrayList<Integer>();
    public int[] inorderTraversal (TreeNode root) {
        // write code here
        order(root);
        int[] arr=new int[list.size()];
        for(int i=0;i<list.size();i++){
            arr[i]=list.get(i);
        }
        return arr;
    }

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

发表于 2023-07-03 17:34:04 回复(0)

Java

一颗宏心

import java.util.*;

public class Solution {
   
    public int[] inorderTraversal (TreeNode root) {
        List<Integer> list = new ArrayList<>();
        inOrder(root,list);
        int[] res = new int[list.size()]; 
        for(int i=0;i<list.size();i++){
            res[i] = list.get(i);
        }
        return res;
    }

    public static void inOrder(TreeNode root,List<Integer> list){
        if(root != null) {
           inOrder(root.left,list);
           list.add(root.val);
           inOrder(root.right,list);
        }
    }   
}

发表于 2022-12-02 23:44:20 回复(0)

Java

牛客341319853号

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) {
        // write code here
        ArrayList<Integer> list = new ArrayList<>();
        inorder(list, root);
        int[] mylist = new int[list.size()];
        for(int i=0;i<list.size();i++){
            mylist[i] = list.get(i);
        }
        return mylist;

    }
    public void inorder(ArrayList<Integer> list, TreeNode root){
        if(root == null){
            return;
        }
        inorder(list, root.left);
        list.add(root.val);
        inorder(list, root.right);
    }
}

发表于 2022-11-13 17:44:46 回复(0)

Java

dynamo1

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) {
         // write code here
        if (root == null) {
            return new int[0];
        }
        List<Integer> list = new ArrayList<Integer>();
        traversal(root, list);
      
        return list.stream().mapToInt(i->i).toArray();
    }

    private void traversal(TreeNode root, List<Integer> list) {
       
        if(root.left != null) {
        traversal(root.left,list);
        }
          list.add(root.val);
          
         if(root.right != null) {
        traversal(root.right,list);
        }
    }
}

发表于 2022-11-04 07:44:32 回复(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)

Java

牛客74558465号

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) {
// write code here
List<Integer> list = new ArrayList<>();
inorder(list,root);
int[] arr = new int[list.size()];
for(int i = 0; i < list.size(); i++){
arr[i] = list.get(i);
}
return arr;
}
public void inorder(List<Integer> list , TreeNode root){
if(root != null){
inorder(list , root.left);
list.add(root.val);
inorder(list , root.right);
}
}
}

发表于 2022-08-31 22:25:14 回复(0)

Java

程序员大鹏

public int[] inorderTraversal (TreeNode root) {
        // write code here
        
        List<TreeNode> resultList = new ArrayList();
        readTree(root,resultList);
        
        int size = resultList.size();
        int[] result = new int[size];
        
        for(int i = 0;i<size; i++) {
            result[i] = resultList.get(i).val;
        }
        return result;
    }
    
    private void readTree(TreeNode root,List<TreeNode> resultList) {
        
        if(null == root) {
            return ;
        }
        
        TreeNode leftNode = root.left;
        readTree(leftNode,resultList);
        
        if(null != root) {
            resultList.add(root);            
        }
        
        TreeNode rightNode = root.right;
        readTree(rightNode,resultList);

    }

发表于 2022-08-31 18:42:35 回复(0)

Java

牛客用户007

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) {
        // write code here
        if (root == null) return new int[0];
        ArrayList<Integer> list = new ArrayList();
        Stack<TreeNode> stack = new Stack();

        while (!stack.isEmpty() || root != null) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                TreeNode node = stack.pop();
                list.add(node.val);
                root = node.right;
            }
        }

        int[] res = new int[list.size()];
        for (int i = 0; i < res.length; i ++) {
            res[i] = list.get(i);
        }

        return res;
    }
}

发表于 2022-08-25 15:44:04 回复(0)

Java

山藏千秋不语

    //morris
    public int[] inorderTraversal (TreeNode root) {
        // write code here
        List<Integer> list = new ArrayList<>();
        TreeNode pre = null;
        while(root != null){
            if(root.left != null){
                pre = root.left;
                while(pre.right != null && pre.right != root){
                    pre = pre.right;
                }
                if(pre.right == null){
                    pre.right = root;
                    root = root.left;
                }else{
                    pre.right = null;
                    list.add(root.val);
                    root = root.right;
                }
            }else{
                list.add(root.val);
                root = root.right;
            }
        }
        int[] ans = new int[list.size()];
        for(int i = 0; i<list.size();i++){
            ans[i] = list.get(i);
        }
        return ans;
    }

发表于 2022-08-18 10:53:25 回复(0)

Java

624huiguorou

中序遍历，同理

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整型一维数组
     */
    
    ArrayList<Integer> l = new ArrayList<>();
    
    public int[] inorderTraversal (TreeNode root) {
        // write code here
        inorder(root);
        int[] r = new int[l.size()];
        for(int i = 0; i < l.size(); i++){
            r[i] = l.get(i);
        }
        return r;
    }
    
    public void inorder(TreeNode root){
        if(root != null){
            //LDR
            inorder(root.left);
            l.add(root.val);
            inorder(root.right);
        }
    }
}

发表于 2022-07-23 19:26:26 回复(0)

Java

yxjing

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) {
        // write code here
        List<Integer> visited=new ArrayList<Integer>();
        inorder(root,visited);
        int[] array=new int[visited.size()];
        for(int i=0;i<=visited.size()-1;i++){
            array[i]=visited.get(i);
        }
        return array;
    }
    public void inorder(TreeNode root,List<Integer> visited){
        if(root==null){return;}
        inorder(root.left,visited);
        visited.add(root.val);
        inorder(root.right,visited);
    }
    
}

发表于 2022-07-15 15:53:35 回复(0)

提交观点

问题信息

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

难度：

33条回答 294收藏 7533浏览

通过挑战的用户

查看代码

苦难精算师

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，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题