38寻找二叉树的最近公共祖先39序列化和反序列化

38.寻找二叉树的最近公共祖先

这题和上一题的区别在于这不是二叉搜索树，无法根据值的大小来判断节点的位置，于是需要遍历

法1 递归写法

递归在左右子树寻找o1和o2

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        return helper(root,o1,o2).val;

    }
    public TreeNode helper(TreeNode root, int o1, int o2){
        if(root==null||root.val==o1||root.val==o2){
            return root;
        }
        TreeNode left = helper(root.left,o1,o2);
        如果left为空，说明这两个节点在root结点的右子树上，我们只需要返回右子树查找的结果
        TreeNode right = helper(root.right,o1,o2);
        if(left==null) return right;
        if(right==null) return left;
        如果left和right都不为空，说明这两个节点一个在root的左子树上一个在root的右子树上，
    //我们只需要返回cur结点即可。
        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

时间复杂度：O（n），n是二叉树节点的个数，最坏情况下每个节点都会被访问一遍
空间复杂度：O（n），因为是递归，取决于栈的深度，最差最差情况下，二叉树退化成链表，栈的深度是n。

法2 BFS（层次遍历/队列）

思路是用层次遍历找到o1和o2,同时用MAP记录每个节点的parent节点，从o1o2出发向上寻找第一个相同的parent节点

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        Map<Integer,Integer> parent = new HashMap<>();
        //存每个节点对应的父节点的值
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        parent.put(root.val,root.val);
        while(!q.isEmpty()||!parent.containsKey(o1)||!parent.containsKey(o2)){
            TreeNode node = q.poll();
            if(node.left!=null){
                q.offer(node.left);
                parent.put(node.left.val,node.val);
            }
            if(node.right!=null){
                q.offer(node.right);
                parent.put(node.right.val,node.val);
            }
        }
        //已经遍历到o1o2两个节点，并存好每个节点对应的parent
        HashSet<Integer> set = new HashSet<>();
        while(!set.contains(o1)){
            set.add(o1);
            o1 = parent.get(o1);//变成父节点 到root会停止
        }//将root到o1的路径上的点全部存起来
        while(!set.contains(o2)){
            set.add(o2);
            o2 = parent.get(o2);
        }//和o2路径上的判断，从下往上，第一个相同的就是结果
        return o2;

    }

}
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

时间复杂度：O（n），n是二叉树节点的个数，最坏情况下每个节点都会被访问一遍
空间复杂度：O（n），一个是BFS需要的队列，一个是父子节点关系的map

39. 序列化二叉树

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
import java.util.*;
public class Solution {
    String Serialize(TreeNode root) {
        ArrayList<String> list = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        if(root==null) return "";
        list.add(Integer.toString(root.val));
        q.offer(root);
        while(!q.isEmpty()){
            TreeNode node = q.poll();
            if(node.left!=null){
                q.offer(node.left);
                list.add(Integer.toString(node.left.val));
            }else list.add("#");
            if(node.right!=null){
                q.offer(node.right);
                list.add(Integer.toString(node.right.val));
            }else list.add("#");
        }
        int flag=0;//去掉最后面的#
        for(int i=list.size()-1; i>=0;i--){
            if(list.get(i)!="#") flag=1;
            if(flag==0&&list.get(i)=="#")
                list.remove(i);
            
        }
        //System.out.println(String.join(",", list));
        return String.join(",", list);//用，来标记，否则不知道具体数值的划分
        
    }
    TreeNode Deserialize(String str) {
        if(str.length()==0) return null;
        Queue<TreeNode> q = new LinkedList<>();
        System.out.println(str);
        System.out.println(str.length());
        int num = 0;
        int i=0;
        while(i < str.length()&&str.charAt(i)!=','){
            num = num*10+str.charAt(i)-'0';
            i++;
        }
        i++;//跳过，
        TreeNode root = new TreeNode(num);
        System.out.println(num);
        q.offer(root);
        while(i < str.length()){
            num = 0;      
            TreeNode node = q.poll();

            if(i < str.length()&&str.charAt(i)=='#'){
                i +=2;    //跳过#和,        
            }
            else if(i < str.length()){
                while(i < str.length()&&str.charAt(i)!=','){
                    num = num*10+str.charAt(i)-'0';
                    i++;
                }
                node.left = new TreeNode(num);
                System.out.println(num);
                q.offer(node.left); 
                i++;
            }
            num=0;
            if(i < str.length()&&str.charAt(i)=='#'){
                i +=2;    //跳过#和,        
            }
            else if(i < str.length()){
                while(i < str.length()&&str.charAt(i)!=','){
                    num = num*10+str.charAt(i)-'0';
                    i++;
                }
                node.right = new TreeNode(num);
                System.out.println(num);
                q.offer(node.right); 
                i++;
            }
        }
        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
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

用层次遍历，时间和空间复杂度都是O(n). 感觉这题考的完全是数组的操作，写的时候百度了很久，看了题解发现有更合适的操作，有可边长数组stringBuilder,反序列的时候可以直接用str.split来划分。

用split和**Integer.parseInt()**可以将反序列的代码简化为

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
import java.util.*;
public class Solution {
    String Serialize(TreeNode root) {
        ArrayList<String> list = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        if(root==null) return "";
        list.add(Integer.toString(root.val));
        q.offer(root);
        while(!q.isEmpty()){
            TreeNode node = q.poll();
            if(node.left!=null){
                q.offer(node.left);
                list.add(Integer.toString(node.left.val));
            }else list.add("#");
            if(node.right!=null){
                q.offer(node.right);
                list.add(Integer.toString(node.right.val));
            }else list.add("#");
        }
        int flag=0;
        for(int i=list.size()-1; i>=0;i--){
            if(list.get(i)!="#") flag=1;
            if(flag==0&&list.get(i)=="#")
                list.remove(i);
            
        }
        System.out.println(list);
        return String.join(",", list);
        
    }
    TreeNode Deserialize(String str) {
        if(str.length()==0) return null;
        Queue<TreeNode> q = new LinkedList<>();
        String[] ss = str.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(ss[0]));
        q.offer(root);
        for(int i = 1; i < ss.length;){    
            TreeNode node = q.poll();
            if(!ss[i].equals("#")){
                node.left = new TreeNode(Integer.parseInt(ss[i]));
                q.offer(node.left); 
                i++;        
            }else i++;
            
            if(i < ss.length&&!ss[i].equals("#")){
                node.right = new TreeNode(Integer.parseInt(ss[i]));
                q.offer(node.right); 
                i++;
            }else i++;
        }
        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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

!!!注意这里判断两个字符串是否相同要用**equals()方法，不能直接用==！！！因为包装类用==只是判断两个对象是否一致，用equals()**才是判断值是否相同。