leetcode 94. Binary Tree Inorder Traversal 二叉树中序递归遍历

骑猪看日落 2022-06-08 01:27 130阅读 0赞

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\].

这个题很简单，就是二叉树的中序遍历。

代码如下：

import java.util.ArrayList;
    import java.util.List;
    
    /*class TreeNode 
    {
        int val;
         TreeNode left;
         TreeNode right;
         TreeNode(int x) { val = x; }
    }*/
    
    /*
     * 二叉树的只中序遍历
     * */
    public class Solution
    {
        
        List<Integer> res=new ArrayList<Integer>();
        public List<Integer> inorderTraversal(TreeNode root) 
        {
            if(root==null) 
                return res;
            ByReci(root);
            return res;
        }
        private void ByReci(TreeNode root)
        {
            if(root ==null )
                return;
            else
            {
                ByReci(root.left);
                res.add(root.val);
                ByReci(root.right);
            }
    
        }
    }

就是二叉树的中序遍历，直接DFS深度优先遍历即可

代码如下：

#include<iostream>
    #include <vector>
    
    using namespace std;
    
    /*
    struct TreeNode
    {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    */
    
    class Solution 
    {
    public:
        vector<int> res;
        vector<int> inorderTraversal(TreeNode* root) 
        {
            getAll(root);
            return res;
        }
    
        void getAll(TreeNode* root)
        {
            if (root == NULL)
                return;
            else
            {
                getAll(root->left);
                res.push_back(root->val);
                getAll(root->right);
            }
        }
    };