[872] 叶子相似的树

[872] 叶子相似的树
[https://leetcode-cn.com/problems/leaf-similar-trees/](https://leetcode-cn.com/problems/leaf-similar-trees/)
	请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列
	举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。
	如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。
	如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false

根据前序遍历获得树的叶子节点,再比较两个树的叶子节点顺序是否一致

``` Cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    //前序遍历获取叶子节点
    void GetTreeNodeList(TreeNode* root, vector<int> &node_list)
    {
        if(root == nullptr) return;

//是叶子节点
        if(root->left == nullptr && root->right == nullptr)
        {
            node_list.push_back(root->val);
        }
        
        GetTreeNodeList(root->left,node_list);      //递归左子树
        GetTreeNodeList(root->right,node_list);     //递归右子树
    }

bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        if(root1 == nullptr && root2 == nullptr) return true;
        if(root1 == nullptr || root2 == nullptr) return false;

vector<int> root1_node;
        vector<int> root2_node;

//获取两个树的叶子节点
        GetTreeNodeList(root1,root1_node);
        GetTreeNodeList(root2,root2_node);

if((int)root1_node.size() != (int)root2_node.size()) return false;

//判断叶子节点是否一致
        for(int i = 0; i < (int)root1_node.size(); ++i)
        {
            if(root1_node[i] != root2_node[i]) return false;
        }

return true;
    }
};