LeetCode#94

LeetCode#94二叉树的中序遍历

题目链接

二叉树的中序遍历，首先我们来看一下二叉树的前序（VLR）、中序（LDR）、后序（LRD）遍历的定义:

前序遍历：先访问根节点，再遍历左子树，最后遍历右子树

中序遍历：先遍历左子树，再访问根节点，最后遍历右子树

后序遍历：先遍历左子树，再访问右子树，最后访问根节点

有了三种遍历的定义，我们在举个例子具体看一下：

先序遍历：123564

中序遍历：153624

后续遍历：563421

结合这个具体的例子是不是就理解了呢？

理解了中序遍历，代码就很好理解了，先判断当前节点是否右左子树，如果有则继续遍历，没有则直接将当前节点存入答案，最后再遍历右子树。

class Solution {
public:
    vector<int>ans;
    void dfs(TreeNode* node)
    {1
        if(node ->left != nullptr)
            dfs(node -> left);
        ans.push_back(node -> val);
        if(node -> right != nullptr)
            dfs(node -> right); 
    }
    vector<int> inorderTraversal(TreeNode* root) {
        if(root == nullptr)
            return ans;
        dfs(root);
        return ans;
    }
};