LeetCode94. Binary Tree Inorder

1、题目链接

https://leetcode.com/problems/binary-tree-inorder-traversal/

2、解题思路

3、代码

非递归：

public static List<Integer> inorderTraversal(TreeNode root) {
    Stack<TreeNode> nodeStack = new Stack<>();
    List<Integer> resultList = new ArrayList<>();
    while (null != root || nodeStack.size() > 0) {
        if (null != root) {
            nodeStack.push(root);
            root = root.left;
        } else {
            root = nodeStack.pop();
            resultList.add(root.val);
            root = root.right;
        }
    }
    return resultList;
}

递归：

public static List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> resultList = new ArrayList<>();
    recursionGetRoot(resultList, root);
    return resultList;
}
public static void recursionGetRoot(List<Integer> resultList, TreeNode root) {
    if (null != root.left) {
        recursionGetRoot(resultList, root.left);
    }
    resultList.add(root.val);
    if (null != root.right) {
        recursionGetRoot(resultList, root.right);
    }
}

4、结果

QQ20190620-141434@2x.png