872. Leaf-Similar Trees

迷南。 2022-04-22 21:34 148阅读 0赞

Consider all the leaves of a binary tree.  From left to right order, the values of those leaves form a *leaf value sequence.*

![tree.png][]

For example, in the given tree above, the leaf value sequence is `(6, 7, 4, 9, 8)`.

Two binary trees are considered *leaf-similar* if their leaf value sequence is the same.

Return `true` if and only if the two given trees with head nodes `root1` and `root2` are leaf-similar.

**Note:**

*  Both of the given trees will have between `1` and `100` nodes.

/**
     * 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:
        bool leafSimilar(TreeNode* root1, TreeNode* root2) {
            vector<int> res1 = GetSeq(root1);
            vector<int> res2 = GetSeq(root2);
            if(res1.size()!= res2.size())
               return false;
            for(int i = 0; i<res1.size(); i++)
            {
              if(res1[i]!= res2[i])
                 return false;
            }
            return true;
        }
    
    private:
       vector<int> GetSeq(TreeNode* root)
        {
           vector<int> result;
            if(root == NULL)
              return result;
            stack<TreeNode*> stackNode;
            while(root!=NULL || !stackNode.empty())
            {         
                while(root)
                {
                    if(root->left == NULL && root->right == NULL)
                    {
                      result.push_back(root->val);
                     }
                  stackNode.push(root);
                  root = root->left;
                }
                         
                TreeNode* temp = stackNode.top();
                stackNode.pop();                  
                root = temp->right;
            }
            return result;
        }
    };

[tree.png]: /images/20220327/5f956bc617f74f39b601a03928bec5a9.png