236. Lowest Common Ancestor of a Binary Tree
发布时间:2020-12-14 04:17:46 所属栏目:大数据 来源:网络整理
导读:? ? 1 // New 2 class Solution { 3 public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q) { 4 if (root == null ) return null ; 5 if (root.val == p.val || root.val == q.val){ 6 return root; 7 } 8 TreeNode left = lowestComm
? ? 1 //New 2 class Solution { 3 public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q) { 4 if(root == null) return null; 5 if(root.val == p.val || root.val == q.val){ 6 return root; 7 } 8 TreeNode left = lowestCommonAncestor(root.left,p,q); 9 TreeNode right = lowestCommonAncestor(root.right,q); 10 if(left != null && right != null){ 11 return root; 12 }else{ 13 return (left != null ? left : right); 14 } 15 16 } 17 } ? ? 1 class Solution { 2 public TreeNode lowestCommonAncestor(TreeNode root,TreeNode q) { 3 if(root == null || p == null || q == null) return null; 4 if(root.val == p.val || root.val == q.val) return root; 5 boolean f1 = false,f2 = false; 6 f1 = dfs(root.left,p) || dfs(root.left,q); 7 f2 = dfs(root.right,p) || dfs(root.right,q); 8 if(f1 && f2){ 9 return root; 10 }else if(f1){ 11 return lowestCommonAncestor(root.left,q); 12 }else if(f2){ 13 return lowestCommonAncestor(root.right,q); 14 } 15 return null; 16 17 } 18 19 public boolean dfs(TreeNode root,TreeNode node){ 20 if(root == null) return false; 21 if(root.val == node.val) return true; 22 return dfs(root.left,node) || dfs(root.right,node); 23 } 24 25 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |