94.二叉树的中序遍历.md

94.二叉树的中序遍历

url

题目

给定一个二叉树的根节点 root ，返回它的 中序 遍历。

输入：root = [1,null,2,3]
输出：[1,3,2]

方法

code

js

var inorderTraversal = function(root) {
    let ret = [];
    if (root === null)
        return ret;
    let stack = [];
    let cur = root;
    while (cur !== null || stack.length !== 0) {
        while (cur !== null) {
            stack.push(cur);
            cur = cur.left;
        }
        let t = stack.pop();
        ret.push(t.val)
        cur = t.right;
    }
    return ret;
};

go

func inorderTraversal(root *TreeNode) []int {
	var ret []int
	if root == nil {
		return ret
	}
	var stack []*TreeNode
	cur := root
	for cur != nil || len(stack) != 0 {
		for cur != nil {
			stack = append(stack, cur)
			cur = cur.Left
		}
		t := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		ret = append(ret, t.Val)
		cur = t.Right
	}
	return ret
}

java

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if (root == null)
            return ret;
        Stack<TreeNode> stack = new Stack<>();

        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode t = stack.pop();
            ret.add(t.val);
            cur = t.right;
        }
        return ret;
    }
}