leetcode-94-中序遍历

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

示例:

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

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

public class TestUtil {
    public static void main(String[] args) {
        Struct s1 = new Struct();
        s1.setValue(1);
        Struct s2 = new Struct();
        s2.setValue(2);
        Struct s3 = new Struct();
        s3.setValue(3);

        s1.setRight(s2);
        s1.setLeft(null);
        s2.setLeft(s3);
        s2.setRight(null);
        s3.setLeft(null);
        s3.setRight(null);

        List<Integer> res = new ArrayList<>();
        inOrderTraversal(s1, res);
        System.out.println(JSON.toJSONString(res));

        res = new ArrayList<>();
        inOrderStack(s1, res);
        System.out.println(JSON.toJSONString(res));

        res = new ArrayList<>();
        inOrderLine(s1, res);
        System.out.println(JSON.toJSONString(res));


    }

    // 递归
    public static void inOrderTraversal(Struct root, List<Integer> res) {
        if (root != null) {
            if (root.getLeft() != null) {
                inOrderTraversal(root.getLeft(), res);
            }

            res.add(root.getValue());

            if (root.getRight() != null) {
                inOrderTraversal(root.getRight(), res);
            }
        }
    }

    // 栈-迭代
    public static void inOrderStack(Struct root, List<Integer> res) {
        Stack<Struct> stack = new Stack<>();
        Struct curr = root;
        while(curr != null || ! stack.empty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.getLeft();
            }

            Struct tmp = stack.pop();
            res.add(tmp.getValue());

            curr = tmp.getRight();
        }
    }

    // 栈-迭代
    public static void inOrderLine(Struct root, List<Integer> res) {
        Struct curr = root;
        while (curr != null) {
            if (curr.getLeft() == null) {
                res.add(curr.getValue());
                curr = curr.getRight();
            } else {
                Struct pre = curr.getLeft();
                while (pre.right != null) {
                    pre = pre.right;
                }

                pre.right = curr;
                Struct tmp = curr;
                curr = curr.getLeft();
                tmp.left = null;
            }
        }
    }
}



class Struct {
    int value;
    Struct left;
    Struct right;

    public void setValue(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }

    public void setLeft(Struct left) {
        this.left = left;
    }

    public Struct getLeft() {
        return left;
    }

    public void setRight(Struct right) {
        this.right = right;
    }

    public Struct getRight() {
        return right;
    }
}