二叉树的中序遍历

94.二叉树的中序遍历

题意

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

二叉树的 中序遍历: 从根节点开始，首先遍历左子树，然后访问根节点，最后访问右子树。然后在遍历左子树的时候，同样首先遍历左子节点的左子树，然后访问根节点，最后遍历左子节点的右子树...

思路一（递归）

按照中序遍历的过程，对每个节点的进行相同的递归处理。先处理这个节点的左子树，再处理这个节点，最后处理这个节点的右子树。

递归终点：当处理的节点是空节点时，说明该节点的子树是空子树，无法继续向下处理了，递归结束，向上返回结果。

代码：

Java

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        LinkedList<Integer> res = new LinkedList<>();
        if (root == null){
            return res;
        }

        res.addAll(inorderTraversal(root.left));  // 先处理左子树
        res.add(root.val);                      // 再处理当前节点
        res.addAll(inorderTraversal(root.right));  // 最后处理右子树

        return res;
    }
}

C++

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        dfs(root, ans);
        return ans;
    }

    void dfs(TreeNode* root, vector<int>& ans){
        if (root == nullptr) return;

        dfs(root->left, ans);   // 先处理左子树
        ans.push_back(root->val);   // 再处理当前节点
        dfs(root->right, ans);   // 最后处理右子树
    }
};

思路二（迭代）

在递归的方法中，其实隐式地维护了一个栈结构：一直递归寻找最下层的左节点，直到找到并处理完后，再返回处理上一层找到的节点。类似于栈中的先进后出，最后找到的节点处理完后，才会处理之前找到的节点。

因此利用迭代的思想，使用一个栈，迭代地寻找当前节点的左子节点，找到后处理并弹出，同理再处理该节点和该节点的右子节点。全部弹出后，最后返回上一层，即当前节点的父节点。此时父节点相当于当前节点，当前节点相当于左节点，继续上述迭代处理即可。

代码：

Java

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();  
        TreeNode node = root;
        Stack<TreeNode> st = new Stack<>();
        // 节点不为空或栈内有节点时，说明还有节点未遍历
        while (!st.isEmpty() || node != null) {
            // 中序遍历，优先遍历当前node为根的子树的最左侧节点
            while (node != null) {
                st.push(node);
                node = node.left;
            }

            node = st.pop();    // 获取当前节点
            res.add(node.val);
            node = node.right;  // 遍历node的右子树
        }

        return res;
    }
}

C++

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;  
        TreeNode* node = root;
        stack<TreeNode*> st;
        // 节点不为空或栈内有节点时，说明还有节点未遍历
        while (!st.empty() || node) {
            // 中序遍历，优先遍历当前node为根的子树的最左侧节点
            while (node) {
                st.push(node);
                node = node->left;
            }

            node = st.top();    // 获取当前节点
            st.pop();           // 弹出栈顶节点
            res.emplace_back(node->val);
            node = node->right;  // 遍历node的右子树
        }
        
        return res;
    }
};