「力扣」第 94 题：二叉树的中序遍历（中等）

专题 12：树

发布日期: 2017-11-22

「力扣」第 94 题：二叉树的中序遍历（中等）

链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/。

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

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

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

方法一：递归

Java 代码实现：

public class Solution {

    private List<Integer> result = new ArrayList<>();

    public List<Integer> inorderTraversal(TreeNode root) {
        inorder(root);
        return result;
    }

    private void inorder(TreeNode root) {
        if (root != null) {
            inorder(root.left);
            result.add(root.val);
            inorder(root.right);
        }
    }
}

方法二：非递归写法 1

Java 代码：

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

public class Solution {

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode currentNode = root;
        while (currentNode != null || !stack.isEmpty()) {
            while (currentNode != null) {
                stack.addLast(currentNode);
                currentNode = currentNode.left;
            }
            currentNode = stack.removeLast();
            res.add(currentNode.val);
            currentNode = currentNode.right;
        }
        return res;
    }
}

方法三：非递归写法 2

Java 代码实现：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

enum UseType {
    RECURSION,
    ADD
}

class Command {
    UseType useType;
    TreeNode treeNode;

    Command(UseType useType, TreeNode treeNode) {
        this.useType = useType;
        this.treeNode = treeNode;
    }
}

/**
 * 什么是中序遍历，先递归遍历左子节点
 * 在处理自己
 * 然后再递归遍历右子节点
 */
public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Stack<Command> stack = new Stack<>();
        stack.push(new Command(UseType.RECURSION, root));

        while (!stack.isEmpty()) {
            Command command = stack.pop();
            if (UseType.ADD == command.useType) {
                result.add(command.treeNode.val);
            } else {
                assert UseType.RECURSION == command.useType;
                if (command.treeNode.right != null) {
                    stack.push(new Command(UseType.RECURSION, command.treeNode.right));
                }
                stack.push(new Command(UseType.ADD, command.treeNode));
                if (command.treeNode.left != null) {
                    stack.push(new Command(UseType.RECURSION, command.treeNode.left));
                }
            }

        }
        return result;
    }
}