リートコード

LeetCode-DFSおよびBFSの質問



Leetcode Dfs Bfs Questions



記事のディレクトリ

98.二分探索木を検証する

二分木が与えられたら、それが有効な二分探索木（BST）であるかどうかを判別します。

BSTが次のように定義されていると仮定します。



  • ノードの左側のサブツリーには、ノードのキーよりも小さいキーを持つノードのみが含まれています。
  • ノードの右側のサブツリーには、ノードのキーよりも大きいキーを持つノードのみが含まれています。
  • 左右のサブツリーもバイナリ検索ツリーである必要があります。
    画像
    問題解決のアイデア： 最も直感的な考え方は、シーケンスがBSTのポストオーダーに従って順序付けられることです。したがって、ツリーを1回ポストオーダーし、シーケンスを保存して、それが順序付けられたシーケンスであるかどうかを判断するだけで済みます。コード1を参照してください。実際、ソリューション1はシーケンスを保存する必要がありますが、これは最良のアルゴリズムではありません。解決策2：トラバーサルプロセス中にルートノードと前のノードの間のサイズの関係を決定します。コード2を参照してください。解決策2はネチズンを参照します グランドヤン 解決。
  1. コード1
/** * 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: void helper(TreeNode *root, vector<int> &res) { if (!root) return helper(root->left, res) res.push_back(root->val) helper(root->right, res) } bool isValidBST(TreeNode* root) { if (!root) return true vector<int> res helper(root, res) for (int i = 1 i < res.size() ++i) { if (res[i - 1] >= res[i]) return false } return true } }
  1. コード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 inorder(TreeNode* node, TreeNode* &pre) { if (!node) return true bool res = inorder(node->left, pre) if (!res) return false if (pre) { if (node->val <= pre->val) return false } pre = node return inorder(node->right, pre) } bool isValidBST(TreeNode* root) { TreeNode *pre = NULL return inorder(root, pre) } }

101.対称ツリー

二分木が与えられたら、それがそれ自体の鏡であるかどうかを確認します（つまり、その中心を中心に対称になります）。
画像
問題解決のアイデア： タイトルは2つの解決策を示唆しています。最初に再帰的解を与えます。コード1を参照してください。ここで反復解を与えます。反復解は本質的にシーケンスのトラバースですが、シーケンスに従ってトラバースされる場合、ノードは空のときにキューに入れられません。このように、層のシーケンスを判断する場合、シーケンスの対​​称性に基づいてツリーが対称であるかどうかを判断することはできません。したがって、空のノードをキューに入れ、シーケンスに存在しない値に空のノードを割り当てる必要があります。ここでは、INT_MINが使用されます。

  1. 再帰的ソリューション
/** * 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 helper(TreeNode* p, TreeNode* q) { if (p == NULL && q == NULL) return true else if (p == NULL || q == NULL) return false else { if (p->val == q->val) return helper(p->left, q->right) && helper(p->right, q->left) return false } } bool isSymmetric(TreeNode* root) { if (!root) return true return helper(root->left, root->right) } }
  1. 反復法
/** * 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 isSymmetric(TreeNode* root) { if (root == NULL) return true queue<TreeNode*> q{{root}} while (!q.empty()) { vector<int> t for (int i = q.size() i > 0 --i) { TreeNode *node = q.front() q.pop() if (node == NULL) t.push_back(INT_MIN) else { t.push_back(node->val) q.push(node->left) q.push(node->right) } } int i = 0, j = t.size() - 1 while (i < j) { if (t[i++] != t[j--]) return false } } return true } }

494.目標合計

非負の整数a1、a2、…、an、およびターゲットSのリストが与えられます。これで、2つの記号+と-ができました。整数ごとに、新しい記号として+と-から1つを選択する必要があります。



整数の合計をターゲットSに等しくするためにシンボルを割り当てる方法がいくつあるかを調べます。
画像
問題解決のアイデア： 深さ優先探索を調べます。

class Solution { public: int findTargetSumWays(vector<int>& nums, int S) { int res = 0 helper(nums, S, 0, res) return res } void helper(vector<int> &nums, long S, int start, int &res) { if (start >= nums.size()) { if (S == 0) ++res return } helper(nums, S - nums[start], start + 1, res) helper(nums, S + nums[start], start + 1, res) } }