首页 > 试题广场 >

二叉树的中序遍历

[编程题]二叉树的中序遍历
  • 热度指数：21085 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
给出一棵二叉树，返回这棵树的中序遍历
例如：
给出的二叉树为{1,#,2,3},
1
\
2
/
3
返回[1,3,2].

备注：递归的解法太没有新意了，你能用迭代的方法来解这道题吗？
示例1

输入

{1,#,2,3}

输出

[1,3,2]

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
M00N头像 M00N 
import java.util.*;
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> ret = new ArrayList<>();
        if (root == null) {
        	return ret;
        }
        
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode temp = root;
        
        while (!stack.isEmpty()) {
            //temp为根，一直向左，并入栈，直到空
        	while (temp != null) {
        		if (temp.left != null) {
        			stack.push(temp.left);
        		}
        		temp = temp.left;
        	}
        	//左孩子为空，访问完毕
        	//访问根
        	temp = stack.pop();
        	ret.add(temp.val);
            //右移，若不空，入栈，做为新的根
            temp = temp.right;
        	if (temp != null) {
        		stack.push(temp);
        	}
        }
        return ret;
    }
}

发表于 2017-04-03 22:12:26 回复(0)
更多回答
JacobGo！头像 JacobGo！ 
/*
	 * 非递归实现二叉树的中序遍历
	 */
	public ArrayList<Integer> inorderTraversal(TreeNode root) {
		Stack<TreeNode> stack = new Stack<TreeNode>();
		ArrayList<Integer> res = new ArrayList<Integer>();
		TreeNode node = root;
		while (!stack.isEmpty() || node != null) {
			while (node != null) {
				stack.push(node);
				node = node.left;
			}

			node = stack.pop();
			res.add(node.val);
			node = node.right;

		}
		return res;
	}

编辑于 2018-05-27 16:20:21 回复(7)
C/C++
nbgao头像 nbgao 
class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> result;
        if(!root)
        	return result;
        stack<TreeNode*> s;
        TreeNode *p=root;
        while(!s.empty() || p!=NULL)
        {
        	while(p)
        	{
	        	s.push(p);
	        	p=p->left;	
			}
			if(!s.empty())
			{
				p = s.top();
				s.pop();
				result.push_back(p->val);
				p = p->right;
			}
		}
		return result;
    }
};

发表于 2017-07-27 01:03:28 回复(4)
HW柯可头像 HW柯可 
//中序遍历递归算法
import java.util.*;
public class Solution {
    ArrayList<Integer> res=new ArrayList<Integer>();
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        if(root==null)
            return res;
        inorder(root,res);
        return res;
    }
    public void inorder(TreeNode root,ArrayList<Integer> res){
        if(root!=null){
            inorder(root.left,res);
            res.add(root.val);
            inorder(root.right,res);
        }
    }
}
//中序遍历非递归算法
import java.util.*;
public class Solution {
    ArrayList<Integer> res=new ArrayList<Integer>();
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        if(root==null)
            return res;
        inorder(root,res);
        return res;
    }
    public void inorder(TreeNode root,ArrayList<Integer> res){
         Stack<TreeNode> stack=new Stack<>();
         TreeNode node=root;
         while(node!=null||!stack.isEmpty()){
             if(node!=null){
                 stack.push(node);
                 node=node.left;
             }
             else{
                 node=stack.pop();
                 res.add(node.val);
                 node=node.right;
             }
         }
    }
}

编辑于 2018-09-25 16:13:18 回复(0)
比丘q头像 比丘q 
class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        stack<TreeNode*> st;
        vector<int> res;
        if(root==nullptr)
            return res;
        TreeNode *cur=nullptr;
        st.push(root);
        while(!st.empty()){
            cur=st.top();
            if(cur->left==nullptr&&cur->right==nullptr){
                res.push_back(cur->val);
                st.pop();
            }
            if(cur->right){
                st.pop();
                st.push(cur->right);
                st.push(cur);
                cur->right=nullptr;
            }
            if(cur->left){
                st.push(cur->left);
                cur->left=nullptr;
            }
        }
        return res;
    }
};


发表于 2019-09-25 10:36:03 回复(0)
Java
安徒生的谎言头像 安徒生的谎言 
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;
public class Solution {
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        if(root==null) {
            return new ArrayList<>();
        }
        ArrayList<Integer> list=new ArrayList<>();
        list.addAll(inorderTraversal(root.left));
        list.add(root.val);
        list.addAll(inorderTraversal(root.right));
        return list;
    }
}

发表于 2018-03-06 10:22:17 回复(0)
啊实打实的阿斯顿是头像 啊实打实的阿斯顿是
用大概bfs方法无递归遍历 

class Solution:
    def inorderTraversal(self , root ):
        # write code here
        res = []
        if not root: return res
        stk = [root]
        visited_left = set() # set用来记录谁往左遍历过，下次就不遍历了
        while stk:
            tmp_cur = stk[-1] #每次拿最上面的点
            i = len(stk) - 1 
            # 开始遍历找到不能再往左的点，同时压栈
            while tmp_cur not in visited_left and tmp_cur.left:
                visited_left.add(tmp_cur)  # 往左走过就记住，下次不会了
                stk.append(tmp_cur.left)
                tmp_cur = tmp_cur.left
                i += 1 
            # 中序输出
            res.append(tmp_cur.val)
            # 没有左边的点，就往右走一个
            if tmp_cur.right:
                stk.append(tmp_cur.right)
                tmp_cur = tmp_cur.right
            # 左右都走过的点出栈
            stk.pop(i)
        return res


编辑于 2020-12-28 13:41:14 回复(0)
Java
LiberHome头像 LiberHome 
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        //一眼就看出来是DFS中序啦，Tree就是这样，麻烦是麻烦，套路比较固定
        /*方法一：
        递归（这里用List）时间复杂度：O(n);空间复杂度：最坏情况下需要空间O(n)，平均情况为O(logn)。*/
        List< Integer > ans = new ArrayList<>();
        helper(root, ans);
        return ans;
    }

    public void helper (TreeNode node, List < Integer > ans){
        if(node != null){
            if(node.left != null){
                helper(node.left, ans);
            }
            ans.add(node.val);
            if(node.right != null){
                helper(node.right, ans);
            }
        }
    }
}
方法二： 
class Solution {
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        //一眼就看出来是DFS中序啦，Tree就是这样，麻烦是麻烦，套路比较固定
        /*方法2：迭代 */
        ArrayList < Integer > ans = new ArrayList < > ();
        Stack < TreeNode > stack = new Stack < > (); //这里用栈实现
        TreeNode curr = root ;
        while(curr != null || !stack.isEmpty()){
            while(curr != null){
                stack.push(curr);
                curr = curr.left;//左
            }
            curr = stack.pop();
            ans.add(curr.val);//中
            curr=curr.right;//右
        }
        return ans;
    }

}


编辑于 2020-07-15 18:10:50 回复(0)
C/C++
努力的牛牛头像 努力的牛牛 
    /*
    * 目的：二叉树中序遍历
    * 方法1：递归
    * 方法2：用栈模拟递归过程
    * 方法3：morris中序遍历，不需要额外空间，以时间换空间
    */
    //方法一：
    void inorder(TreeNode*root, vector<int>&res){
        if (root == nullptr)
            return ;
        inorder(root->left, res);
        res.push_back(root->val);
        inorder(root->right,res);
    }
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int>res;
        inorder(root,res);
        return res;
    }
    //方法二：用栈模拟递归过程
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int>res;
        stack<TreeNode*>st;
        while(root || !st.empty()){
            if (root==nullptr){
                root = st.top();
                st.pop();
                res.push_back(root->val);
                root = root->right;
            }
            else{
                st.push(root);
                root = root->left;
            }
        }
        return res;
    }
    //方法三：morris中序遍历空间复杂度O(1),时间复杂度O（n）
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int>res;
        TreeNode*temp = nullptr;
        while (root){
            if (root->left==nullptr){
                res.push_back(root->val);
                root = root->right;
            }
            else{
                temp = root->left;
                while(temp->right!=nullptr && temp->right!=root){
                    temp = temp->right;
                }
                if (temp->right==nullptr){
                    temp->right = root;
                    root=root->left;
                }
                else{
                    res.push_back(root->val);
                    temp->right = nullptr;
                    root= root->right;
                }
            }
        }
        return res;
    }
发表于 2019-12-08 15:49:52 回复(0)
无心2019头像 无心2019 
class Solution {
public:
    vector<int>res;
    vector<int> inorderTraversal(TreeNode *root) {
        if(root==NULL)
            return res;
        if(root->left!=NULL)
            inorderTraversal(root->left);
        res.push_back(root->val);
        if(root->right!=NULL)
            inorderTraversal(root->right);
        return res;
    }
};

发表于 2019-05-16 19:47:14 回复(0)
LeBronWitness头像 LeBronWitness 
import java.util.ArrayList;

public class Solution {
    private ArrayList<Integer> result;
    
    public Solution() {
        result = new ArrayList<Integer>();
    }
    
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        dfs(root);
        return result;
    }
    
    public void dfs(TreeNode node) {
        if(node==null) return;
        dfs(node.left);
        result.add(node.val);
        dfs(node.right);
    }
}

发表于 2019-05-01 11:53:40 回复(0)
rugu头像 rugu 
class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> ret;
        if(root == NULL)
            return ret;
        stack<TreeNode*> s;
        TreeNode* cur = root;
       
        while(cur != NULL || !s.empty())
        {
            while(cur)
            {
                s.push(cur);
                cur = cur->left;
            }
            if(!s.empty())
            {
                cur = s.top();
                ret.push_back(cur->val);
                s.pop();
                cur = cur->right;
            }
        }
        return ret;       
    }
};

发表于 2018-08-18 14:10:42 回复(0)
C/C++
黄汉韬头像 黄汉韬 
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
/*
思路一：
用栈来模仿递归的过程
每次pop()一次，代表访问了一次该节点。当第二次访问的时候，就可以打印该节点了
可以先画一棵比较完整的二叉树来模拟过程，然后写出代码
思路二：
可以建立线索二叉树来遍历整棵树
*/
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> v;
        if (NULL == root) {
            return v;
        }

        stack<TreeNode*> stk;
        stk.push(root);
        stk.push(root);

        while (!stk.empty()) {
            TreeNode* temp = stk.top(); // 只是起到一个保存记录的作用，并不代表访问了这个节点，访问的操作是pop()
            stk.pop(); // 访问一次该节点

            if ((!stk.empty()) && (temp == stk.top())) {
                if (temp->left != NULL) {
                    stk.push(temp->left);
                    stk.push(temp->left);
                }
            }
            else { // 当第二次访问到这个节点的时候，可以打印了
                v.push_back(temp->val);
                if (temp->right != NULL) {
                    stk.push(temp->right);
                    stk.push(temp->right);
                }
            }
        }

        return v;
    }
};
发表于 2017-11-23 19:49:40 回复(0)
Java
Holiday_12138头像 Holiday_12138 
import java.util.*;
public class Solution {
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        Stack<TreeNode> s = new Stack<TreeNode>();
        while(!s.isEmpty() || root != null) {
            while(root != null) {
                s.push(root);
            	root = root.left;
            }
            root = s.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }
}

发表于 2017-06-25 16:05:13 回复(0)
Java
詆調壹點头像 詆調壹點 
import java.util.*;
public class Solution {
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
		ArrayList<Integer> list = new ArrayList<>();
		Stack<TreeNode> stack = new Stack<>();
		while (root != null || ! stack.isEmpty()) {
			while (root != null) {
				stack.push(root);
				root = root.left;
			}
			root = stack.pop();
			list.add(root.val);
			root = root.right;
		}
		return list;
	}
}

发表于 2017-03-25 18:48:10 回复(0)
C/C++
华科平凡头像 华科平凡

C++ solution

class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> result;
        inorderTra(root, result);
        return result;
    }

    void inorderTra(TreeNode *root, vector<int> &result) {
        if (root == NULL) { return; }
        inorderTra(root->left, result);
        result.push_back(root->val);
        inorderTra(root->right, result);
    }
};
发表于 2017-10-31 14:11:04 回复(2)
我要吃油泼面头像 我要吃油泼面 
import java.util.*;
public class Solution {
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
		return inorder(root, list);        
    }
    public ArrayList<Integer> inorder(TreeNode root, ArrayList<Integer> list){
        if(root == null)
            return list;
        inorder(root.left, list);
        list.add(root.val);
        inorder(root.right, list);
        return list;
    }
}

发表于 2017-05-18 14:15:36 回复(0)
novo头像 novo 
//非递归
class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> ans;
        if(root == NULL) return ans;
        stack<TreeNode* > s;
        TreeNode* p = root;
        while(p != NULL || !s.empty()) {
            while(p != NULL) {
                s.push(p);
                p = p->left;
            }
            if( !s.empty()) {
                p = s.top();
                ans.push_back(p->val);
                s.pop();
                p = p->right;
            }
        }
        return ans;
    }
};

发表于 2016-04-20 14:01:09 回复(0)
Python3
陈*虎头像 陈*虎
class Solution:
    def inorderTraversal(self , root ):
        # write code here
        if root == None: return []
        return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)
发表于 2021-11-06 16:09:37 回复(0)
C++
勇敢牛牛，不怕困难！头像 勇敢牛牛，不怕困难！ 
class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
  vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ans;
    function<void(TreeNode*)> inorder = [&](TreeNode* r) {
      if (!r) return;
      inorder(r->left);
      ans.emplace_back(r->val);
      inorder(r->right);
    };
    inorder(root);
    return ans;
  }
};

发表于 2021-09-18 12:34:18 回复(0)
提交观点

问题信息

树
难度：
75条回答 23932浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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