前言

本系列是hot100补全计划的二叉树篇，主要包含了力扣(leetcode)的二叉树章节部分的习题，除此之外还会有一些比较著名的但不包含在hot100的二叉树题目。

题目

这道题目是leetcode的第94题，链接在这里(点我)。

意思就是以左根右的方式去完成遍历。

思路

tips: 对于二叉树和链表来说，使用递归是一类通用的解题技巧

递归

使用递归法十分简单，这里仅仅贴出代码，不作解释

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private List<Integer> ans = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        dfs(root);
        return ans;
    }
    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        // 先遍历左子树
        dfs(root.left);
        // 把根节点值添加进来
        ans.add(root.val);
        // 接着遍历右子树
        dfs(root.right);
    }
}

比递归方法更难的是迭代法遍历。

迭代

我们知道，递归时默认使用的结构就是栈，也就是Last In First Out，所以，以迭代的方式，我们就可以去手动模拟一个栈出来。

tips：Java中没有直接可以使用的Stack，一般的，我们可以使用LinkedList作为替代

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        // 使用栈来进行模拟
        Deque<TreeNode> st = new LinkedList<>();
        while (root != null || !st.isEmpty()) {
            while (root != null) {
                // 优先遍历所有左子树
                st.push(root);
                root = root.left;
            }
            // 栈顶元素就是左子树结点
            root = st.pop();
            // 根节点
            ans.add(root.val);
            // 右子树
            root = root.right;
        }
        return ans;
    }
}