二叉树的遍历

有两种遍历树的策略：

  • 深度优先搜索(DFS)

    在这个策略中，我们采用深度作为优先级，以便从根开始一直到达某个确定的叶子，然后再返回根到达下一个分支。

    深度优先搜索，又可以根据根节点，左子节点和右子节点的相对顺序被分为 前序遍历 ，中序遍历，后序遍历。

  • 宽度优先搜索(BFS)

    我们按照一层一层访问整棵树，高层次的节点将比低层次的节点先访问到。

如下图中，按照1 2 3 4 5比较不同的策略。

image-20200506155730459

94. 二叉树的中序遍历

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

示例:

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

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：
思路一：

递归，代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

    ArrayList<Integer> list = new ArrayList<>();
    public List<Integer> inorderTraversalRevursive(TreeNode root){
        if (root == null) return list;

        inorderTraversalRevursive(root.left);
        list.add(root.val);
        inorderTraversalRevursive(root.right);

        return list;
    }
思路二：

迭代:

in

代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

    public List<Integer> inorderTraversal(TreeNode root){
        ArrayList<Integer> list = new ArrayList<>();
        if (root == null) return list;

        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null){

            while (node != null){
                stack.push(node);
                node = node.left;
            }

            node = stack.pop();
            list.add(node.val);
            node = node.right;
        }

        return list;
    }