#Leetcode# 235. Lowest Common Ancestor of a Binary Search Tr
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/ ? Given a binary search tree (BST),find the lowest common ancestor (LCA) of two given nodes in the BST. According to the?definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q?as the lowest node in T that has both p and q?as descendants (where we allow?a node to be a descendant of itself).” Given binary search tree:? root =?[6,2,8,4,7,9,null,3,5] ? Example 1: Input: root = [6,5],p = 2,q = 8 Output: 6 Explanation: The LCA of nodes and is . 286 Example 2: Input: root = [6,q = 4 Output: 2 Explanation: The LCA of nodes and is,since a node can be a descendant of itself according to the LCA definition. 242 ? Note:
代码: /** * 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) { int v1 = p -> val; int v2 = q -> val; int r = root -> val; if(v1 > r && v2 < r || v1 < r && v2 > r) return root; if(v1 == r || v2 == r) return root; if(v1 < r) return lowestCommonAncestor(root -> left,p,q); else return lowestCommonAncestor(root -> right,q); } }; 感觉好多递归哦 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |