首页 > itarticle > 算法基础第四课

算法基础第四课

admin 1月 29, 2021 0

遍历的递归行为分析

依次来到节点的顺序是啥？

每个节点会来到三次，这个顺序是不变的，只是我们把打印的时机放在哪，就被加工成了先序，中序和后序

我们把打印的时机放在第一次来到这个节点的时候，就是先序遍历，把打印的时机放在第二次来到这个节点的时候，就是中序遍历，把打印的时机放在第三次来到这个节点的时候，就是后序遍历，

先序遍历

头节点，左子树，右子树

非递归版本

一个栈，先把头结点放进去，然后开始循环，每次先弹出一个节点，然后再进行压栈，先压右，再压左，那么下次弹出的时候，肯定是先弹出左节点，后弹右节点，弹出左节点的时候，还会继续把左孩子的右，左依次压入，所以整体的过程就是先处理当前节点。然后左子树，处理完之后，再处理右子树；

中序遍历

左子树，头节点，右子树

非递归版本

准备一个栈，遍历整个树，当前节点一定会先把自己左边界都压到栈中，直到走到了最下面的左边界。

当前节点为空，从栈拿一个，打印，然后赋给当前节点，然后当前节点往右边跑

当前节点不为空，当前压入栈，当前节点往左走，

压一留左边界，然后依次往外弹，弹到每一个节点，再去遍历它右孩子这个过程，就模拟了左中右这个过程，

后序遍历

左子树，右子树，头节点

非递归版本

先序遍历是 中左右，那么可以很容易的改为 ：中右左，然后打印的时候不打印，把每个节点放进栈中，最后在倒出来打印，就是左右中；

代码：

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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
 
public class  {
    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) {
            Stack<Node> stack = new Stack<Node>();
            stack.add(head);
            while (!stack.isEmpty()) {
                head = stack.pop();
                System.out.print(head.value + " ");
                if (head.right != null) {
                    stack.push(head.right);
                }
                if (head.left != null) {
                    stack.push(head.left);
                }
            }
        }
        System.out.println();
    }


    
     * 非递归实现中序遍历
     * 一压，就压左边一留，
     * 所以压一留左边界，再依次往外弹，弹到某一个节点再去遍历它右孩子的过程
     * 实际上就模拟了左，中，右的过程。
     * 整棵树是可以被左边界分解的。
     */
    public static void inOrderUnRecur(Node head) {
        System.out.print("in-order: ");
        if (head != 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();
                    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) {
            Stack<Node> s1 = new Stack<Node>();
            Stack<Node> s2 = new Stack<Node>();
            s1.push(head);
            while (!s1.isEmpty()) {
                head = s1.pop();
                s2.push(head);
                if (head.left != null) {
                    s1.push(head.left);
                }
                if (head.right != null) {
                    s1.push(head.right);
                }
            }
            while (!s2.isEmpty()) {
                System.out.print(s2.pop().value + " ");
            }
        }
        System.out.println();
    }

    
     * 只用一个栈实现后序遍历
     * geek
     */
    public static void posOrderUnRecur2(Node h) {
        System.out.print("pos-order: ");
        if (h != null) {
            Stack<Node> stack = new Stack<Node>();
            stack.push(h);
            Node c = null;
            while (!stack.isEmpty()) {
                c = stack.peek();
                if (c.left != null && h != c.left && h != c.right) {
                    stack.push(c.left);
                } else if (c.right != null && h != c.right) {
                    stack.push(c.right);
                } else {
                    System.out.print(stack.pop().value + " ");
                    h = c;
                }
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node head = new Node(5);
        head.left = new Node(3);
        head.right = new Node(8);
        head.left.left = new Node(2);
        head.left.right = new Node(4);
        head.left.left.left = new Node(1);
        head.right.left = new Node(7);
        head.right.left.left = new Node(6);
        head.right.right = new Node(10);
        head.right.right.left = new Node(9);
        head.right.right.right = new Node(11);

        // recursive
        System.out.println("==============recursive==============");
        System.out.print("pre-order: ");
        preOrderRecur(head);
        System.out.println();
        System.out.print("in-order: ");
        inOrderRecur(head);
        System.out.println();
        System.out.print("pos-order: ");
        posOrderRecur(head);
        System.out.println();

        // unrecursive
        System.out.println("============unrecursive=============");
        preOrderUnRecur(head);
        inOrderUnRecur(head);
        posOrderUnRecur1(head);
        posOrderUnRecur2(head);
    }
}

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

1
2
3
4
5
6
7
 
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. 如果这个节点没有右子树，就找这个节点是作为哪个节点的左子树的最后一个节点，这个节点就是它的后继节点。

    找的方法就是通过这个节点的父指针，找到父节点，如果这个节点是这个父节点的右孩子，就继续往上找，一直到某一个节点是它父节点的左孩子，这个父节点就是我们要找的节点的后继节点；

代码：

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
 

 * 寻找一颗二叉树节点的后继节点（中序遍历的下一个节点）
 * 1.如果这个节点有右子树，那么后继节点一定是这个右子树上最左的节点。
 * 2.如果这个节点没有右子树，那么就考察这个节点到底作为哪一个节点左子树的最后一个节点。
 * X没有右子树，通过X的父指针找到X的父节点，如果X是父节点的右孩子，继续往上走，直到某个X节点是它父节点的左孩子停止。
 * 此时的父节点就是原始X节点的后继。
 */
public class Code_03_SuccessorNode {
   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) {//x节点不是父节点的左孩子，就一直向上找，直到X节点是父节点的左孩子，返回父节点（就是后继节点）
              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;
    }

   public static void main(String[] args) {
     Node head = new Node(6);
        head.parent = null;
     head.left = new Node(3);
        head.left.parent = head;
     head.left.left = new Node(1);
       head.left.left.parent = head.left;
       head.left.left.right = new Node(2);
     head.left.left.right.parent = head.left.left;
        head.left.right = new Node(4);
      head.left.right.parent = head.left;
      head.left.right.right = new Node(5);
        head.left.right.right.parent = head.left.right;
      head.right = new Node(9);
       head.right.parent = head;
        head.right.left = new Node(8);
      head.right.left.parent = head.right;
     head.right.left.left = new Node(7);
     head.right.left.left.parent = head.right.left;
       head.right.right = new Node(10);
        head.right.right.parent = head.right;

       Node test = head.left.left;
      System.out.println(test.value + " next: " + getSuccessorNode(test).value);
       test = head.left.left.right;
     System.out.println(test.value + " next: " + getSuccessorNode(test).value);
       test = head.left;
        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
       test = head.left.right;
      System.out.println(test.value + " next: " + getSuccessorNode(test).value);
       test = head.left.right.right;
        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
       test = head;
     System.out.println(test.value + " next: " + getSuccessorNode(test).value);
       test = head.right.left.left;
     System.out.println(test.value + " next: " + getSuccessorNode(test).value);
       test = head.right.left;
      System.out.println(test.value + " next: " + getSuccessorNode(test).value);
       test = head.right;
       System.out.println(test.value + " next: " + getSuccessorNode(test).value);
       test = head.right.right; // 10's next is null
       System.out.println(test.value + " next: " + getSuccessorNode(test));
 }
}

序列化和反序列化

先序序列化

遇到null需要加一个特殊符号标记遇到null了

反序列化

按层序列化

代码：

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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
 
public class Code_04_SerializeAndReconstructTree {

   public static class Node {
      public int value;
      public Node left;
       public Node right;

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

   
    * 序列化
   */
   public static String serialByPre(Node head) {
     if (head == null) {
            return "#!";
        }
        String res = head.value + "!";
       res += serialByPre(head.left);
       res += serialByPre(head.right);
      return res;
 }

   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;
    }

    /**
     * 层序  序列化
     */
   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;
 }

    /**
     * 层序  反序列化
     */
  public static Node reconByLevelString(String levelStr) {
      String[] values = levelStr.split("!");
       int index = 0;
      Node head = generateNodeByString(values[index++]);
       Queue<Node> queue = new LinkedList<Node>();
     if (head != null) {
            queue.offer(head);
       }
        Node node = null;
       while (!queue.isEmpty()) {
          node = queue.poll();
         node.left = generateNodeByString(values[index++]);
           node.right = generateNodeByString(values[index++]);
          if (node.left != null) {
               queue.offer(node.left);
          }
            if (node.right != null) {
              queue.offer(node.right);
         }
        }
        return head;
    }

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

   // 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();
  }

   public static void main(String[] args) {
     Node head = null;
       printTree(head);

        String pre = serialByPre(head);
      System.out.println("serialize tree by pre-order: " + pre);
       head = reconByPreString(pre);
        System.out.print("reconstruct tree by pre-order, ");
     printTree(head);

        String level = serialByLevel(head);
      System.out.println("serialize tree by level: " + level);
     head = reconByLevelString(level);
        System.out.print("reconstruct tree by level, ");
     printTree(head);

        System.out.println("====================================");

     head = new Node(1);
     printTree(head);

        pre = serialByPre(head);
     System.out.println("serialize tree by pre-order: " + pre);
       head = reconByPreString(pre);
        System.out.print("reconstruct tree by pre-order, ");
     printTree(head);

        level = serialByLevel(head);
     System.out.println("serialize tree by level: " + level);
     head = reconByLevelString(level);
        System.out.print("reconstruct tree by level, ");
     printTree(head);

        System.out.println("====================================");

     head = new Node(1);
     head.left = new Node(2);
        head.right = new Node(3);
       head.left.left = new Node(4);
       head.right.right = new Node(5);
     printTree(head);

        pre = serialByPre(head);
     System.out.println("serialize tree by pre-order: " + pre);
       head = reconByPreString(pre);
        System.out.print("reconstruct tree by pre-order, ");
     printTree(head);

        level = serialByLevel(head);
     System.out.println("serialize tree by level: " + level);
     head = reconByLevelString(level);
        System.out.print("reconstruct tree by level, ");
     printTree(head);

        System.out.println("====================================");

     head = new Node(100);
       head.left = new Node(21);
       head.left.left = new Node(37);
      head.right = new Node(-42);
     head.right.left = new Node(0);
      head.right.right = new Node(666);
       printTree(head);

        pre = serialByPre(head);
     System.out.println("serialize tree by pre-order: " + pre);
       head = reconByPreString(pre);
        System.out.print("reconstruct tree by pre-order, ");
     printTree(head);

        level = serialByLevel(head);
     System.out.println("serialize tree by level: " + level);
     head = reconByLevelString(level);
        System.out.print("reconstruct tree by level, ");
     printTree(head);

        System.out.println("====================================");

 }
}

判断是否是平衡二叉树

定义：

任一一个节点的左右子树高度差相差不超过1

套路：

递归函数很好用！
一个节点会回到自己三次，遍历的时候一次，
遍历左子数完成又回来一次
遍历右子树完又回来一次
总共三次。
大套路就是：既然可以回到一个节点三次，就想办法收集一下左子树上的信息，再想办法收集一下右子树上的信息，
然后把这个信息做整合来判断。整棵树符不符合我们的标准

针对这道题目就是：如果以每一个节点作为头结点的树都是平衡树，那么整棵树都是平衡树。

如何判断以x为头结点的整棵树是不是平衡的？

需要收集那些信息

  1. 左子树是否平衡
  2. 右子树是否平衡
  3. 左子树的高度
  4. 右子树的高度

列出可能性，整理出返回值的类型，整个递归过程按照同样的结构，得到子树的信息，整合子树的信息，加工出我的信息，往上返回，要求结构完全一致，因为是递归函数。这是最大的套路， 它不能帮你解决列出可能性，怎么解决这道题的思路，但是可以给你一个方法论，以及写代码会非常快，什么方法论？你就想我就会遍历每一个节点，考虑以每个节点为头的整棵树怎么怎么样，都判断完，这道题就出来了，整个大的方法论就是这样一个过程，然后左树收集什么信息，右树收集什么信息，列出可能性， 是你要去想的，也就仅是列出可能性这个问题是你需要想的，接下来怎么写代码完全套路的；


代码：

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
 
public class Code_06_IsBalancedTree {
    public static class Node {
        public int value;
        public Node left;
        public Node right;

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

    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;
    }

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


    //===============第二种方法=================================
    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);
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
        head.right.right = new Node(7);

        System.out.println(isBalance(head));
    }
}

判断是否是搜索二叉树

对于任何一个节点，左子树都比它小，右子树都比它大，就是搜索二叉树，

二叉树中序遍历后，是升序排列的，就是搜索二叉树，否则就不是

使用非递归版本的中序遍历过程，在遍历的过程中，用一个变量记录上一个值，在打印的时候，进行比较，比上一个值小，说明肯定不是搜索二叉树

判断是否是完全二叉树

判断是否是完全二叉树：按层遍历

判断逻辑

  1. 如果一个节点有右孩子但是没有左孩子，直接返回false；
  2. 如果一个节点不是左右孩子双全，（有左没右，或者左右都没有，有右没左的情况在1中已经排除了）。则后面的节点都必须是叶子节点

遍历完既不违反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
140
141
142
143
144
145
146
147
148
149
 
public class Code_07_IsBSTAndCBT {
    public static class Node {
      public int value;
      public Node left;
       public Node right;

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

    /**
     * 自己用非递归中序遍历的方式实现
     * 如何判断是否是搜索二叉树：中序遍历是从小到大排序的。
     * 中序遍历是升序的。
     */
    public static boolean isBSTinTraver(Node head){

        Stack<Node> stack = new Stack<Node>();

        int lastNum = Integer.MIN_VALUE;
        while(!stack.isEmpty() || head != null){
            if(head != null){
                stack.push(head);
                head = head.left;
            }else{
                head = stack.pop();
                if(head.value < lastNum){
                    return false;
                }else{
                    lastNum = head.value;
                }
                head = head.right;
            }
        }

        return true;
    }


    /**
     * 所谓的more死什么遍历
     * 这个先不用看
     */
  public static boolean isBST(Node head) {
     if (head == null) {
            return true;
       }
        boolean res = true;
        Node pre = null;
        Node cur1 = head;
        Node cur2 = null;
       while (cur1 != null) {
         cur2 = cur1.left;
            if (cur2 != null) {
                while (cur2.right != null && cur2.right != cur1) {
                 cur2 = cur2.right;
               }
                if (cur2.right == null) {
                  cur2.right = cur1;
                   cur1 = cur1.left;
                    continue;
               } else {
                    cur2.right = null;
              }
            }
            if (pre != null && pre.value > cur1.value) {
                res = false;
            }
            pre = cur1;
          cur1 = cur1.right;
       }
        return res;
 }

   public static boolean isCBT(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;       //可以这么写的原因是左孩子为null，右孩子不为null在情况一已经抛弃掉了。
            }
        }
        return true;
   }

    // 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();
  }

   public static void main(String[] args) {
     Node head = new Node(4);
        head.left = new Node(2);
        head.right = new Node(6);
       head.left.left = new Node(1);
       head.left.right = new Node(3);
      head.right.left = new Node(5);

     printTree(head);
     System.out.println(isBST(head));
     System.out.println(isCBT(head));

    }
}

已知一颗完全二叉树，求其节点的个数

要求：时间复杂度低于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
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
 
/**
 * 求一颗完全二叉树的子节点个数
 * 时间复杂度：每一层遍历的节点个数只会有一个，一共有O（logN）层。
 * 到了这个节点，还会遍历这个节点右子树的最左边的边界，又是O（logN），
 * 所以时间复杂度是O（logN）的平方
 */
public class Code_08_CompleteTreeNodeNumber {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

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

    /**
     *  主函数
     *  一定是完全二叉树
     */
    public static int nodeNum(Node head) {
        if (head == null) {
            return 0;
        }
        return bs(head, 1, mostLeftLevel(head, 1));
    }

    /**
     * @param node  当前节点
     * @param level 当前节点在第几层，
     * @param h      整棵树的深度（层数）
     * @return      以node为头的整棵树的节点个数
     */
    public static int bs(Node node, int level, int h) {
        if (level == h) {  //level是最后一层，说明node是叶子节点，所以以node为头的整棵树节点个数是一个。
            return 1;
        }
        if (mostLeftLevel(node.right, level + 1) == h) {//node的右子树的最左的深度到没到整体最深的深度。
            return (1 << (h - level)) + bs(node.right, level + 1, h);//说明node的左子树是一颗完全二叉树，深度是level-1.
        } else {
            return (1 << (h - level - 1)) + bs(node.left, level + 1, h);
        }
    }

    /**
     * @param node
     * @param level
     * @return  整棵树最左的边界到了哪一层。
     */
    public static int mostLeftLevel(Node node, int level) {
        while (node != null) {
            level++;
            node = node.left;
        }
        return level - 1;
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
        System.out.println(nodeNum(head));

    }
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能