我要招人

去企业版

首页 > 试题广场 >

二叉树的中序遍历

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

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

算法知识视频讲解

Java

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)

Java

吭哧吭哧埋头干

/**
 * 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) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        Stack<TreeNode> stack=new Stack<TreeNode>();
        TreeNode node=root;
        while(!stack.isEmpty()||node!=null){
            while(node!=null){
                stack.push(node);
                node=node.left;
            }
            node=stack.pop();
            list.add(node.val);
            node=node.right;
        }         return list;
    }
}

发表于 2018-09-04 16:44:39 回复(0)

Java

七仔0312

递归

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<>();
        if (root == null)
            return result;
        result.addAll(inorderTraversal(root.left));
        result.add(root.val);
        result.addAll(inorderTraversal(root.right));

        return result;
    }
}

import java.util.*;
public class Solution {
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<>();
        if (root == null)
            return result;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            if (!stack.isEmpty()) {
                node = stack.pop();
                result.add(node.val);
                node = node.right;
            }
        }

        return result;
    }
}

发表于 2018-03-16 22:03:05 回复(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)

Java

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)

Java

城市里的养猫者

public List<Integer> inorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode cur = root; while(cur!=null || !stack.empty()){ while(cur!=null){ stack.add(cur);
            cur = cur.left;
        }
        cur = stack.pop(); list.add(cur.val);
        cur = cur.right;
    } return list;
}