Commitcb66901

committed

MEDIUM/src/medium/LowestCommonAncestorOfABinaryTree.java

1 parent6363289 commitcb66901Copy full SHA for cb66901

File tree

+18

-0

lines changed

+18

-0

lines changed

Lines changed: 18 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,18 @@`
	`1`	`+packagemedium;`
	`2`	`+`
	`3`	`+importclasses.TreeNode;`
	`4`	`+`
	`5`	`+publicclassLowestCommonAncestorOfABinaryTree {`
	`6`	`+//we need to find TWO nodes in the tree, so we'll have to divide and conquer this tree, we need to have two nodes to as the intermediate`
	`7`	`+//result, inspired by this one: https://discuss.leetcode.com/topic/18566/my-java-solution-which-is-easy-to-understand`
	`8`	`+//Also, refer to my earlier drawings:http://www.fishercoder.com/2016/06/23/lowest-common-ancestor-of-a-binary-tree/`
	`9`	`+//I'm really impressed with myself at that time!`
	`10`	`+publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq) {`
	`11`	`+if(root ==null \|\|root ==p \|\|root ==q)returnroot;`
	`12`	`+TreeNodeleft =lowestCommonAncestor(root.left,p,q);`
	`13`	`+TreeNoderight =lowestCommonAncestor(root.right,p,q);`
	`14`	`+if(left !=null &&right !=null)returnroot;`
	`15`	`+returnleft !=null ?left :right;`
	`16`	`+ }`
	`17`	`+`
	`18`	`+}`

Comments

(0)