首页 > 试题广场 >

二叉树的中序遍历

[编程题]二叉树的中序遍历
  • 热度指数：88569 时间限制：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，点此查看相关信息
算法知识视频讲解
添加回答
Java
Naaaaaaaaaaasus头像 Naaaaaaaaaaasus
家人们, {1, 2, 3, #, #, 4} 这种输入是什么含义啊？能画张图吗？# 代表什么？
如果再复杂一点, {1,2,3,4,6,9} 这个二叉树长啥样？
发表于 2024-01-31 09:36:35 回复(0)
Java
Frank.HUANG头像 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
无糖COLA头像 无糖COLA 
深度优先搜索-递归
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头像 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号头像 牛客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头像 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号头像 牛客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头像 牛客用户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头像 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头像 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)
Java
牛客191072895号头像 牛客191072895号

非递归前中后序使用同一套模板：

前序遍历：

import java.util.*;
public class Solution {
    public int[] inorderTraversal (TreeNode root) {
     if(root == null) return new int[0];
        Stack<NodeWithStatus> st = new Stack<NodeWithStatus>();
        st.push(new NodeWithStatus(root,1));
        List<Integer> list = new ArrayList<>();
        while(!st.isEmpty()){
            NodeWithStatus nws = st.peek();
            if(nws.status == 1){
                //前序遍历
                list.add(nws.node.val);
                if(nws.node.left != null){
                    NodeWithStatus nodeWithStatus = new NodeWithStatus(nws.node.left,1);
                    st.push(nodeWithStatus);
                }
                nws.status = 2;
            }else if(nws.status == 2){
                if(nws.node.right != null){
                    NodeWithStatus nodeWithStatus = new NodeWithStatus(nws.node.right,1);
                    st.push(nodeWithStatus);
                }
                nws.status = 3;
            }else if(nws.status == 3){
                st.pop();
            }
        }
        int size = list.size();
        int[] res = new int[size];
        for(int i = 0; i < size; i++){
            res[i] = list.get(i);
        }
        return res;
    }
}
class NodeWithStatus{
    TreeNode node;
    int status;
    public NodeWithStatus(TreeNode node,int status){
        this.node = node;
        this.status = status;
    }
}

中序遍历

import java.util.*;
public class Solution {
    public int[] inorderTraversal (TreeNode root) {
     if(root == null) return new int[0];
        Stack<NodeWithStatus> st = new Stack<NodeWithStatus>();
        st.push(new NodeWithStatus(root,1));
        List<Integer> list = new ArrayList<>();
        while(!st.isEmpty()){
            NodeWithStatus nws = st.peek();
            if(nws.status == 1){
                if(nws.node.left != null){
                    NodeWithStatus nodeWithStatus = new NodeWithStatus(nws.node.left,1);
                    st.push(nodeWithStatus);
                }
                nws.status = 2;
            }else if(nws.status == 2){
                //中序遍历
                list.add(nws.node.val);
                if(nws.node.right != null){
                    NodeWithStatus nodeWithStatus = new NodeWithStatus(nws.node.right,1);
                    st.push(nodeWithStatus);
                }
                nws.status = 3;
            }else if(nws.status == 3){
                st.pop();
            }
        }
        int size = list.size();
        int[] res = new int[size];
        for(int i = 0; i < size; i++){
            res[i] = list.get(i);
        }
        return res;
    }
}
class NodeWithStatus{
    TreeNode node;
    int status;
    public NodeWithStatus(TreeNode node,int status){
        this.node = node;
        this.status = status;
    }
}

后续遍历：

import java.util.*;
public class Solution {
    public int[] inorderTraversal (TreeNode root) {
     if(root == null) return new int[0];
        Stack<NodeWithStatus> st = new Stack<NodeWithStatus>();
        st.push(new NodeWithStatus(root,1));
        List<Integer> list = new ArrayList<>();
        while(!st.isEmpty()){
            NodeWithStatus nws = st.peek();
            if(nws.status == 1){
                if(nws.node.left != null){
                    NodeWithStatus nodeWithStatus = new NodeWithStatus(nws.node.left,1);
                    st.push(nodeWithStatus);
                }
                nws.status = 2;
            }else if(nws.status == 2){
                if(nws.node.right != null){
                    NodeWithStatus nodeWithStatus = new NodeWithStatus(nws.node.right,1);
                    st.push(nodeWithStatus);
                }
                nws.status = 3;
            }else if(nws.status == 3){
                //后序遍历
                list.add(nws.node.val);
                st.pop();
            }
        }
        int size = list.size();
        int[] res = new int[size];
        for(int i = 0; i < size; i++){
            res[i] = list.get(i);
        }
        return res;
    }
}
class NodeWithStatus{
    TreeNode node;
    int status;
    public NodeWithStatus(TreeNode node,int status){
        this.node = node;
        this.status = status;
    }
}
发表于 2022-07-03 10:14:14 回复(0)
Java
2小时一个题头像 2小时一个题 
   List<Integer> list= new ArrayList<>();
    public int[] inorderTraversal(TreeNode root) {
        // write code here
        if(root ==null) 
            return new int[0];
//         TreeNode downNode =root.left;
        getList(root);
        return list.stream().mapToInt(Integer::valueOf).toArray();
    } 
    public void getList(TreeNode root) {
        // write code here
        if(root.left !=null) {
            getList(root.left);
        }
        list.add(root.val);
        if(root.right !=null){
            getList(root.right);
        }
    }

发表于 2022-06-09 23:20:22 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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