首页 > itarticle > [leetcode] problem 94 – binary tree inorder traversal

[leetcode] problem 94 – binary tree inorder traversal

admin 11月 13, 2020 0

Given a binary tree, return the inorder traversal of its nodes’ values.

Example

Input: [1,null,2,3]

Output: [1,3,2]

Follow up

Recursive solution is trivial, could you do it iteratively?

Code

public class  {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;

    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }

        TreeNode node = stack.pop();
        result.add(node.val);
        current = node.right;
    }

    return result;
}