Contents

236. Lowest Common Ancestor of a Binary Tree

題目 :

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

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).”

Example :

Note

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 Output: 5 Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [1,2], p = 1, q = 2 Output: 1

解題思路 :

• 這題需要我們找出兩nodes的最低共同祖先

• 以下提供兩個解題思路:

1. 第一種(我最一開始想到的): 先做一次preorder並將整棵樹存進stack，在從頭部開始找 p or q 其中一個node，若先找到 p 我就設定target為 q，反之則設target為 p ，並擷取頭部到 p(or q)的slice做為新的stack，這樣做的目的是因為preorder的關係，p 跟 q 的共同祖先們都在此新的stack中，於是我們再把此stack裡的node從尾部一個一個push出來(因為越尾部越接近當初找到的 p(or q))，並以他們為root做preorder找出是否是target的祖先，第一個符合此條件的node便是 p, q的最低共同祖先

2. 第二種‵: 是直接將樹分成兩半做判斷，寫法也很直觀，若找到 p 或 q 就直接回傳該node，若是沒找到就回傳nil，分成兩邊就可以做篩檢，若回傳為nil就直接忽略了，往有找到的那邊繼續往下找，直到兩邊都有找到，那代表該node便是他們的最低共同祖先

Recursive-1解法

• time complexity: O(n^2) , space complexity: O(n)

Runtime: 4 ms, faster than 99.71% of Go online submissions for Lowest Common Ancestor of a Binary Tree.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 `````` ``````/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode { var stack []*TreeNode preorder(root, &stack) var tar *TreeNode for i, v := range stack { if v == p { tar = q stack = stack[:i+1] break } if v == q { tar = p stack = stack[:i+1] break } } res := false for i := len(stack)-1; i >= 0; i-- { findpOrq(stack[i], tar.Val, &res) if res { return stack[i] } } return root } func preorder(node *TreeNode, stack *[]*TreeNode) { if node == nil { return } *stack = append(*stack, node) preorder(node.Left, stack) preorder(node.Right, stack) } func findpOrq(node *TreeNode, tar int, res *bool) { if node == nil { return } if node.Val == tar { *res = true } findpOrq(node.Left, tar, res) findpOrq(node.Right, tar, res) } ``````

Recursive-2解法

• time complexity: O(n) , space complexity: O(1)

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 `````` ``````/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode { if root == nil { return root } if root == p || root == q { return root } left := lowestCommonAncestor(root.Left, p, q) right := lowestCommonAncestor(root.Right, p, q) if left != nil && right != nil { return root } if left != nil { return left } if right != nil { return right } return nil } ``````