[LeetCode 解題筆記] Univalued Binary Tree

原問題網址:965. Univalued Binary Tree

問題描述

一棵 Binary Tree 如果每個 node 的 value 都相等便稱作 univalued。

如果這棵 tree 為 univalued 就 return true

解題思路

利用 Preorder traversal 拜訪每個 node,並且在過程中檢查是否每個 node 的 value 都一樣,一但發現不一樣就 return false

以下為用 C 語言的程式碼:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool preorder_check(struct TreeNode* root, int target_val) {
  if (!root) {
    return true;
  }
  if (root->val != target_val) {
    return false;
  }
  if (!preorder_check(root->left, target_val)) {
    return false;
  }
  if (!preorder_check(root->right, target_val)) {
    return false;
  }
  return true;
}

bool isUnivalTree(struct TreeNode* root){
  return preorder_check(root, root->val);
}
Show Comments