二叉树判断表兄弟表兄妹算法(递归, 深度优先)

这题比较有意思, 拿来分享一下:

在二叉树中, 根节点在深度0处, 并且每个深度k节点的子节点在深度k + 1处. 如果二元树的两个节点具有相同的深度但具有不同的父节点, 则它们是堂/表兄弟. 我们给出了具有唯一值的二叉树的根, 以及树中两个不同节点的值x和y.

当且仅当对应于值x和y的节点是同类时, 才返回true.

例如:

  1
2  3

2和3的父母是同一个, 所以不是表兄弟(妹)

    1
   2 3
  4   5

4和5是, 因为来自不同的父母, 并且所以树的高度是一样的.

深度优先+递归

二叉树(或者图)的一些算法大多数都可以用深度优先DFS来实现, 这题也不例外. 深度优先可以用递归来实现较简单(当然也可以自己写迭代来操作堆栈)

我们可以用一次深度优先DFS来遍历所有节点, 并在过程中记录树结点的深度和父母. 需要用两个哈希表.

/**
 * 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 isCousins(TreeNode* root, int x, int y) {                     
        dfs(root, NULL, 0);
        return (depth[x] == depth[y]) && (parent[x] != parent[y]);
    }
    
    void dfs(TreeNode* root, TreeNode* p, int d) {
        if (root == NULL) return;
        depth[root->val] = d; // 记录深度
        parent[root->val] = p; // 记录父母
        dfs(root->left, root, d + 1);
        dfs(root->right, root, d + 1);
    }

private:
    unordered_map<int, int> depth;
    unordered_map<int, TreeNode*> parent;
};

然后再判断两个节点的父母和高度即可. 时间复杂度是O(N), 空间复杂度也是O(N). N是树的节点个数.

上面的算法我们还可以用稍微不同的实现. 让这个DFS函数同时返回树节点的深度和父节点.

/**
 * 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 isCousins(TreeNode* root, int x, int y) {
        pair<int, TreeNode*> a = dfs(root, x, 0, nullptr);
        pair<int, TreeNode*> b = dfs(root, y, 0, nullptr);
        return (a.first == b.first) && (a.second != b.second);
    }
    
private:
    pair<int, TreeNode*> dfs(TreeNode* root, int val, int depth, TreeNode* parent) {
        // 如果找不到该节点, 就返回特殊值
        if (root == nullptr) {
            return {0, nullptr}; 
        }
        if (root->val == val) {
            return {depth, parent};
        }
        auto a = dfs(root->left, val, depth + 1, root);
        if (a.first != 0) return a;
        auto b = dfs(root->right, val, depth + 1, root);
        return b;        
    }
};

如果内存要求比较严格, 我们可以用4次深度优先来完成这个任务. 获取深度和获取父母需要各检查2次.

/**
 * 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 isCousins(TreeNode* root, int x, int y) {
        TreeNode* leftParent = findParent(root, nullptr, x);
        TreeNode* rightParent = findParent(root, nullptr, y);
        if (leftParent == rightParent) return false;
        int dx = depth(root, 0, x);
        int dy = depth(root, 0, y);
        return dx == dy;
    }
    
private:
    // 得到节点 v 的深度
    int depth(TreeNode* root, int curDepth, int v) {
        if (root == nullptr) return 0;
        if (root->val == v) {
            return curDepth;
        }
        int x = depth(root->left, curDepth + 1, v);
        if (x > 0) return x;
        return depth(root->right, curDepth + 1, v);
    }
    
    // 得到节点 v 的父母
    TreeNode* findParent(TreeNode* root, TreeNode* parent, int v) {
        if (root == nullptr) return nullptr;
        if (root->val == v) return parent;
        TreeNode* left = findParent(root->left, root, v);
        if (left != nullptr) return left;
        return findParent(root->right, root, v);
    }
};

当然上面的算法假定给定的两个节点都能在树中找到, 否则算法会给出不是的结果(也算正常), 不存在的节点返回高度为0, 父母为NULL.

英文: The Cousins in Binary Tree
相关工具: 家庭关系称呼查讯 – 家庭称谓计算器 – 女儿的儿子的哥哥的老婆叫啥?