力扣每日刷题

236. 二叉树的最近公共祖先

解题思路：

对于每个节点来说，如果自己就是目标节点之一，就把自己返回，如果不是则以自己为根节点查看自己的子树中有没有目标节点，如果有一个则返回一个，如果有两个则返回自己（此时自己就是最小的父节点）。

分类讨论：

1. 当两个节点有共同的父节点的时候。
2. 当一个节点在另一个节点的子树上的时候。

当两个目标节点在一个子树上时会直接返回最上面的父节点。

不在同一个子树的时候，那么他们一定分别属于节点的左右子树，当左右节点得到的返回值都不为空时才返回共同的父节点，否则会一直返回目标节点。

代码：

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root==null||root==p||root==q){return root;}TreeNode l=lowestCommonAncestor(root.left,p,q);TreeNode r=lowestCommonAncestor(root.right,p,q);if(l==null){return r;}if(r==null){return l;}return root;}
}

124. 二叉树中的最大路径和

解题思路：

先考虑如何求一颗树的最大值，一颗树的最大值等于左子树的最大值加上右子树的最大值。接下来我们只要遍历每一个棵树就能得出最大的值了。

优化：在之前的思路上对算法进行优化，我们只要提出一个变量用它来保存树的最大值，然后把比较树的最大值的判断语句放在遍历树的语句中，就可以达到O(N)的时间复杂度来解这道题了。

代码：。

class Solution {int max=Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {deep(root);return max;}public int deep(TreeNode root){if(root==null){return 0;}int l=deep(root.left);int r=deep(root.right);max=Math.max(max,l+r+root.val);return Math.max(Math.max(l,r)+root.val,0);}
}