LeetCode:872. Leaf-Similar Trees

Tree DFS

872. Leaf-Similar Trees

题目理解:

给出两棵树, 判断他们由叶子结点组成的序列是否相同

思路:

对树进行从左子树开始的深度优先搜索, 找到叶子结点则放入栈, 最后比较两个栈是否一致

小结:

作业太多, 划水一下

Submission Detail:

code:

class Solution {
public:
    int treeStack1[101], treeStack2[101];
    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        treeStack1[0] = treeStack2[0] = 0;
        findLeaf(root1, treeStack1);
        findLeaf(root2, treeStack2);
        if (treeStack1[0] != treeStack2[0]) {
            return false;
        }
        for (int i = 1; i <= treeStack1[0]; ++i) {
            if (treeStack1[i] != treeStack2[i]) {
                return false;
            }
        }
        return true;
    }
    void findLeaf(TreeNode* node, int* s) {
        if (node->left == nullptr && node->right == nullptr) {
            s[++s[0]] = node->val;
        } else {
            if (node->left != nullptr) {
                findLeaf(node->left, s);
            }
            if (node->right != nullptr) {
                findLeaf(node->right, s);
            }
        }
    }
};