【二叉树的最近公共祖先】【后序遍历】Leetcode 236. 二叉树的最近公共祖先

---------------🎈🎈236. 二叉树的最近公共祖先 题目链接🎈🎈-------------------

解法1 涉及到结果向上返回就要用后序遍历

可以稍微记一下 求二叉树的最近公共祖先，就考虑两个子节点的情况写代码就可以“以偏概全”

时间复杂度分析：
在每个节点上，都进行了常数次操作（比较和赋值），所以时间复杂度为 O(n)，其中 n 是二叉树中的节点数。

空间复杂度分析：
递归调用的栈空间最大深度等于二叉树的高度，所以空间复杂度为 O(h)，其中 h 是二叉树的高度

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 
 // 后序遍历 左右中
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root ==null) return null;
        if(root==p ||root==q) return root;
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);

        if(left == null && right==null) return null;
        else if(left == null && right!=null) return right;
        else if(left != null && right==null) return left;
        else return root;
    }
}
      
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

解法2 自己写的方法 后序遍历

时间复杂度O(N)
空间复杂度O(N)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 后序遍历 左右中
        if(root == null) return null;
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);

        if(left==null && right==null) {
            if(root!=p && root!=q) return null;
            else if(root == p) return p;
            else return q;
        }
        else if(left==null && right!=null) {
            if(root !=p && root!=q){
                return right;
            }
            else{
                return root;
            }
        }
        else if(left!=null && right==null){
            if(root !=p && root!=q){
                return left;
            }
            else{
                return root;
            }
        }
        else{
            return root;
        }    
    }
}

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