LeetCode: 94. Binary Tree Inorder Traversal

题目描述

Given a binary tree, return the inorder traversal of its nodes’ values.

For example:
Given binary tree [1,null,2,3],

   1
    \      2
    /
   3

return [1,3,2].

题目大意： 对二叉树进行中序遍历。

解题思路

  1. 对给定二叉树的根的左子树执行中序遍历;
  2. 输出该二叉树根的值;

  3. 对该二叉树的右子树执行中序遍历;

AC 代码

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> inorderSequence;

        if(root == nullptr) return inorderSequence;

        // 对左子树进行中序遍历
        inorderSequence = inorderTraversal(root->left);

        // 输出根节点
        inorderSequence.push_back(root->val);

        // 对右子树进行中序遍历
        vector<int> rightInorderSequence = inorderTraversal(root->right);
        inorderSequence.insert(inorderSequence.end(),
               rightInorderSequence.begin(), rightInorderSequence.end());

        return inorderSequence;
    }
};