LeetCode124|二叉树的中序遍历

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class InorderTraversalTest2 {
    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        t1.right = t2;
        t2.left = t3;
        List<Integer> list = inorderTraversal2(t1);
        System.out.println("list = " + list);

    }

    private static List<Integer> list = new ArrayList<>();

    public static List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) {
            return list;
        }
        dfs(root);
        return list;
    }

    private static void dfs(TreeNode root) {

        if (root.left != null) {
            dfs(root.left);
        }
        list.add(root.val);
        if (root.right != null) {
            dfs(root.right);
        }
    }

    public static List<Integer> inorderTraversal2(TreeNode root) {
        if (root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode tempNode = root;
        while (!stack.isEmpty() || tempNode != null) {
            while (tempNode != null) {
                stack.push(tempNode);
                tempNode = tempNode.left;
            }
            TreeNode temp = stack.pop();
            list.add(temp.val);
            tempNode = temp.right;

        }
        return list;
    }
}