94. Binary Tree Inorder Traversal

题目描述和难度

• 题目描述：

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

输出: [1,3,2]

• 题目难度：中等。
• 英文网址：94. Binary Tree Inorder Traversal 。
• 中文网址：94. 二叉树的中序遍历 。

思路分析

求解关键：

参考解答

参考解答1：使用递归完成遍历。

Java 实现：

public class Solution2 {

    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);
        }
    }
}

Python 实现：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):

    # 递归解法

    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """

        res = []
        self.__helper(root, res)
        return res

    def __helper(self, node, res):
        if node is None:
            return

        self.__helper(node.left, res)
        res.append(node.val)
        self.__helper(node.right, res)

参考解答2：使用非递归，借助栈完成遍历。

Python 实现：

class Solution(object):

    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        stack = []
        while root or stack:
            # 只要当前遍历的结点不是空结点
            if root:
                stack.append(root)
                root = root.left
            else:
                node = stack.pop()
                res.append(node.val)
                root = node.right
        return res

Python 实现：

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        stack = []
        node = root
        while node or stack:
            while node:
                stack.append(node)
                node = node.left

            node = stack.pop()
            res.append(node.val)
            node = node.right
        return res

参考解答3：

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;
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0094-binary-tree-inorder-traversal ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。