Inorder Tree Traversal (is there any optimal solution than this???)


  • 0
    S
    class Solution {
        vector<int> arr;
    public:
        vector<int> inorderTraversal(TreeNode *root) {
            if(root){
                if(root->left)
                inorderTraversal(root->left);
                arr.push_back(root->val);
                if(root->right)
                inorderTraversal(root->right);
                return arr;
            }
            
            if(!root) return arr;
            
        }
    };

  • 2
    M

    There are one or two major issues with this solution, as well as a couple minor ones.

    First the minor ones. If you put if(!root) return arr; at the top, you don't need the if(root) portion of the first chunk. Otherwise, you don't need if(!root) because the only way to reach it is if root is null. It will always evaluate to true.

    Secondly, depending on how you define optimal, you can remove the if(root->...) checks because the if(root) on the next step will catch it. Timewise it is less efficient, but codewise, it's shorter.

    Now for the major issues. First is one I am not sure of. I think arr will persist between runs, so running it a second time will have all the node values added to the end of an already present traversal.

    Second is the one I'm certain of. This is a recursive algorithm. While the problem is technically solved, the aim of this challenge is to do it iteratively. From the problem:

    Note: Recursive solution is trivial, could you do it iteratively?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.