BinaryTreeInorderTraversal2 [source code]

public class BinaryTreeInorderTraversal2 {
static
/******************************************************************************/
public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null)
            return res;
        Stack<TreeNode> s = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !s.isEmpty()) {
            while (cur != null) {
                s.push(cur);
                cur = cur.left;
            }
            cur = s.pop();
            res.add(cur.val);
            cur = cur.right;
        }
        return res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        BinaryTreeInorderTraversal2.Solution tester = new BinaryTreeInorderTraversal2.Solution();
    }
}

morris的ver1 AC之后, 这里尝试用Stack来做一次;

花了一天的时间彻底总结iterative DFS, 基本初步清扫了所有的知识点, 详情可以看IterativeDFS.java文件里面; 这里就是其中一个我自己优化过的版本; 速度是2ms;

Problem Description

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

For example:
Given binary tree [1,null,2,3],

   1  
    \  
     2  
    /  
   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

Difficulty:Medium
Total Accepted:210.6K
Total Submissions:452.8K
Contributor: LeetCode
Companies
microsoft
Related Topics
tree hash table stack
Similar Questions
Validate Binary Search Tree Binary Tree Preorder Traversal Binary Tree Postorder Traversal Binary Search Tree Iterator Kth Smallest Element in a BST Closest Binary Search Tree Value II Inorder Successor in BST