左神算法-基础课-04

Posted on | In , , ,

题目一 实现二叉树的先序、中序、后序遍历

包括递归方式和非递归方式

递归方式遍历

image-20201120112203883

非递归遍历

先序遍历

  1. 自行准备一个栈，判断头节点非空时，将头节点压入栈中
  2. 以下部分循环：直到栈为空；
    1. 弹出节点，输出
    2. 判断是否有右孩子，有的话压入栈中
    3. 判断是否有左孩子，有的话压入栈中
  3. 打印换行，结束

中序遍历

  1. 准备一个栈，
  2. 循环：当栈为空且当前指针为空时停止
    1. 当前节点不为空：
      • 当前节点压入栈中，当前节点找到左孩子；
    2. 当前节点为空
      • 从栈中弹出给当前节点，打印；然后当前节点找到右孩子；

后序遍历

先序遍历是: 中右左；

后序遍历是：中左右的逆序；可以用到先序遍历的技巧+栈序打印；

也就是再先序遍历打印的位置把它保存起来；逆序打印；所以用到栈结构保存，再弹出打印就很方便；

代码

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
public static class Node {
    public int value;
    public Node left;
    public Node right;

    public Node(int data) {
        this.value = data;
    }
}

public static void preOrderRecur(Node head) {
    if (head == null) {
        return ;
    }
    System.out.print(head.value + " ");
    preOrderRecur(head.left);
    preOrderRecur(head.right);
}

public static void inOrderRecur(Node head) {
    if (head == null) {
        return ;
    }
    inOrderRecur(head.left);
    System.out.print(head.value + " ");
    inOrderRecur(head.right);
}

public static void posOrderRecur(Node head) {
    if (head == null) {
        return ;
    }
    posOrderRecur(head.left);
    posOrderRecur(head.right);
    System.out.print(head.value + " ");
}

public static void preOrderUnRecur(Node head) {
    System.out.print("pre-order: ");
    if (head == null) {
        return ;
    }
    Stack<Node> stack = new Stack<Node>();
    stack.push(head);
    Node tmp = null;
    while (!stack.isEmpty()) {
        tmp = stack.pop();
        System.out.print(tmp.value + " ");
        if (tmp.right != null) {
            stack.push(tmp.right);
        }
        if (tmp.left != null) {
            stack.push(tmp.left);
        }
    }
    System.out.println();
}

public static void inOrderUnRecur(Node head) {
    System.out.print("in-order: ");
    if (head == null) {
        return ;
    }
    Stack<Node> stack = new Stack<Node>();
    while (!stack.isEmpty() || head != null) {
        if (head != null) {
            stack.push(head);
            head = head.left;
        } else {
            head = stack.pop();
            System.out.print(head.value + " ");
            head = head.right;
        }
    }
    System.out.println();
}

public static void posOrderUnRecur1(Node head) {
    System.out.print("pos-order: ");
    if (head == null) {
        return ;
    }
    Stack<Node> stack = new Stack<Node>();
    stack.push(head);
    Stack<Node> stack_p = new Stack<Node>();
    Node tmp;
    while (!stack.isEmpty()) {
        tmp = stack.pop();
        stack_p.push(tmp);
        if (tmp.left != null) {
            stack.push(tmp.left);
        }
        if (tmp.right != null) {
            stack.push(tmp.right);
        }
    }
    while (!stack_p.isEmpty()) {
        System.out.print(stack_p.pop().value + " ");
    }
    System.out.println();
}

public static void posOrderUnRecur2(Node head) {
    System.out.print("pos-order: ");
    if (head != null) {
        Stack<Node> stack = new Stack<Node>();
        stack.push(head);
        Node c = null;
        while (!stack.isEmpty()) {
            c = stack.peek();
            /*
                1. 左节点为空或者它的孩子节点刚被输出过
                    反过来想，这个节点的左孩子不为空，并且左孩子没有被刚输出（没有右孩子），右孩子也没有被刚输出（左孩子可能被输出过了）
                    这种情况下就需要把左孩子压栈
             */
            if (c.left != null && head != c.left && head != c.right) { 
                stack.push(c.left);
            } 
            /*
                2. 右节点为空或者它的右节点刚被输出过；
                    右孩子不为空，并且栈顶结点的右孩子没有被输出过，满足这个条件即可压入栈
                    因为左孩子被上一个判断了，它可能为空，也可能被输出过了。
                    在这一步判断要不要把右孩子加入到栈中不重要；
             */
            else if (c.right != null && head != c.right) {
                stack.push(c.right);
            } 
            /*
               3. 当前栈顶节点的左右孩子要么为空要么被输出了，那么就把它输出了；
             */
            else {    
                // 当前栈顶节点，在以上两个条件同时不满足的情况下输出：
                System.out.print(stack.pop().value + " ");
                head = c;
            }
        }
    }
    System.out.println();
}

题目二 如何直观的打印一颗二叉树

左神说：从上到下的树很难画出来；

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
// for test -- print tree
public static void printTree(Node head) {
    System.out.println("Binary Tree:");
    printInOrder(head, 0, "H", 17);
    System.out.println();
}

public static void printInOrder(Node head, int height, String to, int len) {
    if (head == null) {
        return;
    }
    printInOrder(head.right, height + 1, "v", len);
    String val = to + head.value + to;
    int lenM = val.length();
    int lenL = (len - lenM) / 2;
    int lenR = len - lenM - lenL;
    val = getSpace(lenL) + val + getSpace(lenR);
    System.out.println(getSpace(height * len) + val);
    printInOrder(head.left, height + 1, "^", len);
}

public static String getSpace(int num) {
    String space = " ";
    StringBuffer buf = new StringBuffer("");
    for (int i = 0; i < num; i++) {
        buf.append(space);
    }
    return buf.toString();
}

题目三 在二叉树中找到一个节点的后继节点

题目

现在有一种新的二叉树节点类型如下：

1
2
3
4
5
6
7
8
9
public class Node { 
    public int value; 
    public Node left;
	public Node right; 
    public Node parent;
	public Node(int data) { 
        this.value = data; 
    }
}

该结构比普通二叉树节点结构多了一个指向父节点的parent指针。

假设有一 棵Node类型的节点组成的二叉树，树中每个节点的parent指针都正确地指向 自己的父节点，头节点的parent指向null。

只给一个在 二叉树中的某个节点 node，请实现返回node的后继节点的函数。

在二叉树的中序遍历的序列中， node的下一个节点叫作node的后继节点。

思考

针对一个给定节点，要求出它的后继结点；

首先第一步就是判断它是什么节点：它是其父节点的左孩子，他是其父节点的右孩子，它是根节点；

  • 它是父节点的左孩子
    • 如果它的右子树存在：则返回右子树中序遍历的第一个节点；
    • 如果不存在右子树：则返回其父节点
  • 它是父节点的右孩子
    • 它是父节点的右孩子，那么它的左孩子都已经被中序遍历过了。即只能再看其右孩子；
    • 如果它没有右孩子，那就需要考虑其父节点在树中的位置
  • 它是根节点
    • 找到其右子树中序遍历的第一个节点；

题解

当前节点有右子树，那么返回其右子树上最左的节点

节点右子树不存在：那么当前节点即可被认为是某一节点的左子树中序遍历的最后一个节点；找到这个节点即可；

  • 找到节点的父节点判断节点是其父节点的左孩子或者右孩子：
    • 左孩子：停止，返回这个父节点
    • 右孩子：继续往上找；
    • 空或者自循环：到树的根节点了，则不存在下一个；
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
public static class Node {
    public int value;
    public Node left;
    public Node right;
    public Node parent;

    public Node(int data) {
        this.value = data;
    }
}

public static Node getSuccessorNode(Node node) {
    if (node == null) {
        return node;
    }
    if (node.right != null) {
        return getLeftMost(node.right);
    } else {
        Node parent = node.parent;
        while (parent != null && parent.left != node) {
            node = parent;
            parent = node.parent;
        }
        return parent;
    }
}

public static Node getLeftMost(Node node) {
    if (node == null) {
        return node;
    }
    while (node.left != null) {
        node = node.left;
    }
    return node;
}

题目四 介绍二叉树的序列化和反序列化

序列化

​ 先序遍历：节点和节点之间用一个符号（比如 _）分隔。并且遇到空时用另一个符号（比如 #）来表示。

image-20201125155615990

反序列化

 **按照先序遍历序列化的就按照先序遍历反序列化**

​ 依次取出头节点，再取就是头节点的左节点或者空左孩子；依次完成树的重建；

序列化实现

先序遍历

通过递归的方式：

如果当前节点为空则直接返回 “ #! ” ;

如果不为空，字符串加入头节点的值和分割符 “ ! ” ；

再把字符串后加上当前节点左节点的返回和右节点的返回；

整个函数返回字符串；

1
2
3
4
5
6
7
8
9
public static String serialByPre(Node head) {
    if (head == null) {
        return "#!";
    }
    String res = head.value + "!";
    res += serialByPre(head.left);
    res += serialByPre(head.right);
    return res;
}

层序遍历

如果当前节点为空则直接返回 “ #! ” ;

申请一个队列来保存队列的顺序；

给字符串 res 加上根节点的值以及分割符；

再把根节点加入到队列当中；

持续循环——>直到队列为空：

  • 从队列中取出一个节点；
  • 判断这个节点的左节点是否为空 ？ 字符串加上这个节点的左节点的值以及分割符，队列加入 这个节点的左节点 : 给字符串加上空节点的符号表示
  • 同样的流程判断右节点是否为空；

返回字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static String serialByLevel(Node head) {
    if (head == null) {
        return "#!";
    }
    String res = head.value + "!";
    Queue<Node> queue = new LinkedList<Node>();
    queue.offer(head);
    while (!queue.isEmpty()) {
        head = queue.poll();
        if (head.left != null) {
            res += head.left.value + "!";
            queue.offer(head.left) ;
        } else {
            res += "#!";
        }
        if (head.right != null) {
            res += head.right.value + "!";
            queue.offer(head.right);
        } else {
            res += "#!";
        }
    }
    return res;
}

反序列化实现

前序遍历反序列化

把序列化字符串用分割符分割开成为一个字符串数组；

申请一个保存字符串的队列；

按照前序遍历的方式序列化的，就按照前序遍历的方式反序列化

调用一个从队列反序列化的函数：

  • 从队列中取出第一个节点的字符串。判断它是否是空节点的表示，是的话，返回null；
  • 如果不是，创建节点对象，保存这个值；然后再递归调用自身得到接下来的左子树的表示和右子树的表示；
  • 最终返回头节点；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static Node reconByPreString(String preStr) {
    String[] values = preStr.split("!");
    Queue<String> queue = new LinkedList<String>();
    for (int i = 0; i != values.length ; i++) {
        queue.offer(values[i]);
    }
    return reconPreOrder(queue);
}

public static Node reconPreOrder(Queue<String> queue) {
    String value = queue.poll();
    if (value.equals("#")) {
        return null;
    }
    Node head = new Node(Integer.valueOf(value));
    head.left = reconPreOrder(queue);
    head.right = reconPreOrder(queue);
    return head;
}

层次遍历反序列化

把序列化字符串用分割符分割开成为一个字符串数组；

把字符川数组的第一个字符串转成根节点；

申请一个保存节点的队列；

如果头节点不为空，则把根节点加入进去；

while 循环 ——> 如果队列不为空

  • 从队列中取出一个节点
  • 把字符串数字接下来的值转成节点（也可能为空），赋给取出节点的左节点；
  • 如果左节点不为空则把左节点加入队列
  • 把字符串数字接下来的值转成节点（也可能为空），赋给取出节点的右节点；
  • 如果右节点不为空则把左节点加入队列

返回根节点

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
public static Node reconByLevelString(String levelStr) {
    String[] values = levelStr.split("!");
    int index = 0;
    Node head = generateNodeByString(values[index++]);
    Queue<Node> quene = new LinkedList<Node>();
    if (head != null) {
        quene.offer(head);
    }
    Node node = null;
    while (!quene.isEmpty()) {
        node = quene.poll();
        node.left = generateNodeByString(values[index ++]);
        node.right = generateNodeByString(values[index ++]);
        if (node.left != null) {
            quene.offer(node.left);
        }
        if (node.right != null) {
            quene.offer(node.right);
        }
    }
    return head;
}

public static Node generateNodeByString(String val) {
    if (val.equals("#")) {
        return null;
    }
    return new Node(Integer.valueOf(val));
}

题目五 折纸问题

题目

【题目】 请把一段纸条竖着放在桌子上，然后从纸条的下边向 上方对折1次，压出折痕后展开。此时 折痕是凹下去的，即折痕 突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折 2 次，压出折痕后展开，此时有三条折痕，从上到下依次是下折 痕、下折痕和上折痕。 给定一 个输入参数N，代表纸条都从下边向上方连续对折N次， 请从上到下打印所有折痕的方向。 例如：N=1时，打印： down N=2时，打印： down down up

思路

把纸折一次，它的中间是凹的；它的上部分再折也是凹的；它的下部分再折是凸的；以此类推，就可以得到这个问题的答案；

1
2
3
4
5
6
7
8
9
10
11
12
public static void printAllFolds(int N) {
    printProcess(1, N, true);
}

public static void printProcess(int i, int N, boolean down) {
    if (i > N) {
        return ;
    }
    printProcess(i + 1, N, true);
    System.out.println(down ? "down " : "up ");
    printProcess(i + 1, N, false);
}

题目六 判断一棵树是否是平衡二叉树（AVL）

平衡二叉树 ：一颗树的任意节点左子树与右子树的高度差不超过1；

树算法：递归很好用；因为针对一个节点的递归会返回一个节点三次：他自己，左子树回来，右子树回来；

思考

判断一个节点 x 是否平衡：

  1. 左树是否平衡；
  2. 右数是否平衡；
  3. 左树的高度是什么？
  4. 右数的高度是什么？
  5. 左树与右数高度差是否平衡；

就是需要求左子树与右子树的高度，还要时刻判断当下的树是否平衡：

方法传入了两个值，一个是level表示判断节点的层级，res用了数组。使其能改变自身使值返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static boolean isBalance(Node head) {
    boolean[] res = new boolean[1];
    res[0] = true;
    getHeight(head, 1, res);
    return res[0];
}

public static int getHeight(Node head, int level, boolean[] res) {
    if (head == null) {
        return level;
    }
    int lH = getHeight(head.left, level + 1, res);
    if (!res[0]) {
        return level;
    }
    int rH = getHeight(head.right, level + 1, res);
    if (!res[0]) {
        return level;
    }
    if (Math.abs(lH - rH) > 1) {
        res[0] = false;
    }
    return Math.max(lH, rH);
}

接下来是一个套路化的过程，具体的思想就是把需要求得到信息封装成一个类，然后把这个类打包在每个节点间传递：

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
public static class ReturnData{
    public boolean isB;
    public int h;
    public ReturnData(boolean isB, int h) {
        this.isB = isB;
        this.h = h;
    }
}

public static boolean isB(Node head) {
    return process(head).isB;
}

public static ReturnData process(Node head) {
    if (head == null) {
        return new ReturnData(true, 0);
    }
    ReturnData leftData = process(head.left);
    if (!leftData.isB) {
        return new ReturnData(false,0);
    }
    ReturnData rightData = process(head.right);
    if (!rightData.isB) {
        return new ReturnData(false,0);
    }
    if (Math.abs(leftData.h-rightData.h) > 1) {
        return new ReturnData(false, 0);
    }
    return new ReturnData(true, Math.max(leftData.h, rightData.h));
}

题目七 判断一棵树是否是搜索二叉树、判断一棵树是完全二叉树

搜索二叉树

搜索二叉树：这棵树上任何一个节点为头的子树，这个节点的左子树都比这个节点的数小，右子树都比他大；（中序遍历是依次升序的，充分必要条件）

所以看一个树是否是搜索二叉树，可以直接判断它的中序遍历是否是依次升序的；

所以对于非递归版的中序遍历打印那句，就判断要打印的当前节点是否大于本应该打印的上一个节点，不大于就是不是搜索二叉树，大于就直接更新，找下一个中序节点；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static boolean isBST(Node head) {
    if (head == null) {
        return true;
    }
    Node node = null;
    Stack<Node> stack = new Stack<Node>();
    while (!stack.isEmpty() || head != null) {
        if (head != null) {
            stack.push(head);
            head = head.left;
        } else {
            head = stack.pop();
            if (node!= null && node.value > head.value) {
                System.out.println(node.value+" "+ head.value);;
                return false;
            }
            node = head;
            head = head.right;
        }
    }
    return true;
}

完全二叉树

完全二叉树：算法过程需要按层遍历；

  • 如果一个节点有右孩子，没有左孩子；一定不是完全二叉树；

  • 如果一个节点只有一个左孩子，或者没有孩子，那么它后面遇到的节点都必须是叶节点；否则不是完全二叉树；

（由于情况一违反的话直接就没了，所以判断是否是情况二的情况，右边叶子一定是空；）

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
// 我写的
public static boolean isCBT(Node head) {
    if (head == null) {
        return true;
    }
    Queue<Node> queue = new LinkedList<Node>();
    queue.offer(head);
    Node node;
    boolean leaf = false;
    while (!queue.isEmpty()) {
        node = queue.poll();
        if (node.right != null && node.left != null) {
            if (leaf) {
                return false;
            }
            queue.offer(node.left);
            queue.offer(node.right);
        } else if (node.left == null && node.right != null) {
            return false;
        } else {
            if (node.left != null) {
                if (leaf) {
                    return false;
                }
                queue.offer(node.left);
            }
            leaf = true;
        }
    }
    return true;
}
// 左神简化版
public static boolean isCBT2(Node head) {
    if (head == null) {
        return true;
    }
    Queue<Node> queue = new LinkedList<Node>();
    boolean leaf = false;
    Node l = null;
    Node r = null;
    queue.offer(head);
    while (!queue.isEmpty()) {
        head = queue.poll();
        l = head.left;
        r = head.right;
        if ((leaf && (l != null || r != null)) || (l == null && r != null) ) {
            return false;
        }
        if (l != null) {
            queue.offer(l);
        }
        if (r != null) {
            queue.offer(r);
        } else {
            leaf = true;
        }
    }
    return true;
}

题目八 已知一棵完全二叉树，求其节点的个数

要求：时间复杂度低于O(N)，N为这棵树的节点个数

思路

先遍历完全二叉树根节点到它的最左节点；这样可以判断出完全二叉树的高度；然后再判断右子树的最左节点是否存在；

如果存在则说明他的根节点的左子树是满二叉树：左子树可以通过高度求出来；右子树可以通过递归求得；

如果不存在说明右节点也是满二叉树；则可以由递归求得左子树； 

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
public static int nodeNum(Node head) {
    if (head == null) {
        return 0;
    }
    return bs(head, 1, mostLeftLevel(head, 1));
}

public static int bs(Node node, int level, int h) {
    if (level == h) {
        return 1;
    }

    if (mostLeftLevel(node.right, level + 1) == h){
        return (1 << (h - level)) + bs(node.right, level + 1, h);
    } else {
        return (1 << (h - level - 1)) + bs(node.left, level + 1, h);
    }

}

public static int mostLeftLevel(Node node, int level) {
    while (node != null) {
        level += 1;
        node = node.left;
    }
    return level - 1;
}