二分木

LeetCode 236.バイナリツリーの最も低い共通祖先（2ノードのLCA）



Leetcode 236 Lowest Common Ancestor Binary Tree



タイトルリンク： ここをクリック

画像
画像
これが最も無謀なアプローチで、コードがいっぱいです



分析：

  1. 2ノード 共通祖先 ルートノードからこれら2つのノードへのパス上にある必要があります。
  2. 共通の祖先の 最近の公の祖先 、つまり、両方のパスに表示されるルートノードから最も遠い（または2つに最も近い）ノード。
  3. 最終的なアルゴリズム：pノードパスとqノードパスを見つけてから、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: //Find the path from the root node to a node (depth traversal) //The node the node is traversing, the search node with search, the path path stack, the result storage path result, and whether the finish record is found void preorder(TreeNode* node, TreeNode* search, vector<TreeNode*> &path, vector<TreeNode*> &result, int &finish) { if(!node || finish) return path.push_back(node) if(node==search) { finish = 1 result = path } preorder(node->left, search, path, result, finish) preorder(node->right, search, path, result, finish) path.pop_back() } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { vector<TreeNode*> path //Temporary stack vector<TreeNode*> node_p_path //Store the path of node p vector<TreeNode*> node_q_path //Store the path of node q int finish = 0 preorder(root, p, path, node_p_path, finish) path.clear() //Empty path, finish finish = 0 preorder(root, q, path, node_q_path, finish) int path_len = 0 //The length of the shorter path if(node_p_path.size() < node_q_path.size()) path_len = node_p_path.size() else path_len = node_q_path.size() //Traverse the nodes on two paths at the same time to find the nearest public ancestor TreeNode* result = NULL for(int i = 0 i < path_len i++) if(node_p_path[i]==node_q_path[i]) result = node_p_path[i] return result } }

再帰的思考：



2つのノードp、qは、次の2つのケースに分けられます。

  1. pとqは同じサブツリーにあります
  2. 異なるサブツリーのpとq

ルートノードからトラバースし、ノード情報について左右のサブツリーに再帰的にクエリを実行します。

再帰的終了条件：現在のノードが空またはpまたはqに等しい場合、現在のノードに戻ります。



  1. 左右のサブツリーを再帰的にトラバースします。左と右のサブツリーがノードが空でないことを検出した場合、それはpとqがそれぞれ左と右のサブツリーにあることを意味します。したがって、現在のノードが最も近い共通の祖先です。
  2. 左右のサブツリーの1つが空でない場合、空でないノードが返されます。

LeetCodeファンによって報告されたエラーに注意してください。

/** * 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: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) root==p }