leetcode-872-叶子相似的树

叶子相似的树

题面

leetcode题目

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

example

输入：root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
输出：true

题解

总体思路

这个很简单了，就是中序遍历并且只输出叶子节点。

代码

#include <iostream>
#include <vector>
//#define _DEBUG
using namespace std;
// submit
/**
 * 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:
    bool leafSimilar(TreeNode *root1, TreeNode *root2)
    {
        vector<int> v1, v2;
        solve(root1, v1);
        solve(root2, v2);
#ifdef _DEBUG
        for (int i = 0; i < v1.size(); i++)
        {
            cout << v1[i] << " ";
        }
        cout << endl;
        for (int i = 0; i < v2.size(); i++)
        {
            cout << v2[i] << " ";
        }
        cout << endl;
#endif
        int length = v1.size();
        if (length != v2.size())
        {
            return false;
        }
        for (int i = 0; i < length; i++)
        {
            if (v1[i] != v2[i])
                return false;
        }
        return true;
    }
    void solve(TreeNode *root, vector<int> &ret)
    {
        if (root == NULL)
        {
            return;
        }

        if (root->left == NULL && root->right == NULL)
        {
            ret.push_back(root->val);
            return;
        }
        solve(root->left, ret);
        solve(root->right, ret);
    }
};

// for test
int main()
{
    Solution s;

    return 0;
}