94. 二叉树的中序遍历

94. 二叉树的中序遍历

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

示例:

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

代码实现

• 迭代

public List<Integer> inorderTraversal(TreeNode root) {

        LinkedList<Integer> linkedList = new LinkedList<>();
        if (root == null) return linkedList;
        TreeNode node = root;
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || node != null){
            if (node != null){
                stack.push(node);
                node = node.left;
            }else {
                TreeNode topNode = stack.pop();
                linkedList.add(topNode.val);
                node = topNode.right;
            }
        }
        return linkedList;
    }

• 递归

LinkedList<Integer> linkedList = new LinkedList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) return linkedList;
        inorderTraversal(root.left);
        linkedList.add(root.val);
        inorderTraversal(root.right);
        return linkedList;
    }

解题思路

• 迭代实现
  利用栈实现

1. 设置 node 等于 root
2. 循环执行以下操作
   2.1. 如果node不等于null，将node入栈，设置将node的左子节点赋值给node
   2.2. 如果node等于null
   2.2.1. 如果栈为空，结束遍历，
   2.3.2. 如果栈不为空，弹出栈顶元素进行访问，并将栈顶元素的右子节点赋值给node

• 递归实现

1. 中序遍历左子树
2. 访问根节点
3. 中序遍历右子树