首页 > itarticle > 左神基础算法笔记-四

左神基础算法笔记-四

admin 10月 28, 2020 0

1. 二叉树先序、中序、后序遍历的非递归实现

先序遍历：使用栈实现，栈中先压入二叉树根节点，然后循环以下过程，先弹出一个节点，随后压入该节点的右孩子，再压入该节点的左孩子……（这样弹出时就是左孩子先弹出，右孩子再弹出，满足先序）

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
 

 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class  {
    public List<Integer> preorderTraversal(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
        LinkedList<Integer> output = new LinkedList<Integer>();
        if(root == null){
            return output;
        }
        
        stack.add(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pollLast();
            output.add(node.val);
            if(node.right!=null){
                stack.add(node.right);
            }
            if(node.left!=null){
                stack.add(node.left);
            }
        }
        return output;
    }
}

中序遍历：栈不为空时开始循环，先压入左边界，然后弹出，再处理右子树，右子树也是这样的逻辑，先压入右子树的左边界，再处理右子树的右子树……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
class  {
    public List<Integer> inorderTraversal(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        List<Integer> res = new ArrayList<>();
        TreeNode curr = root;
        while(curr != null || !stack.isEmpty()){
            while(curr != null){
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            res.add(curr.val);
            curr = curr.right;
        }
        return res;
    }
}

中序拓展~中右左

后序遍历：中右左反过来，使用 help 栈；打印的时候不打印但是压入 help 栈，弹出即为后序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
class  {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
        LinkedList<Integer> output = new LinkedList<Integer>();
        if(root == null){
            return output;
        }
        
        stack.add(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pollLast();
            output.addFirst(node.val);
            if(node.left != null){
                stack.add(node.left);
            }
            if(node.right != null){
                stack.add(node.right);
            }
        }
        return output;
    }
}

2. 如何直观的打印一颗二叉树

将打印结果顺时针旋转 90° 即为一棵二叉树，H 代表头节点，^ 代表该节点的父节点在左上方，v 代表该节点的父节点在左下方。

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
 
public class PrintBinaryTree {

   public static void printTree(TreeNode head) {
      System.out.println("Binary Tree:");
      printInOrder(head, 0, "H", 17);
      System.out.println();
   }

   public static void printInOrder(TreeNode head, int height, String to, int len) {
      if (head == null) {
         return;
      }
      printInOrder(head.right, height + 1, "v", len);
      String val = to + head.val + 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) {
      TreeNode head = new TreeNode(1);
      head.left = new TreeNode(-222222222);
      head.right = new TreeNode(3);
      head.left.left = new TreeNode(Integer.MIN_VALUE);
      head.right.left = new TreeNode(55555555);
      head.right.right = new TreeNode(66);
      head.left.left.right = new TreeNode(777);
      printTree(head);

      printTree(head);

   }

}

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

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

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
 
public static TreeNode getSuccessorNode(TreeNode node) {
        if (node == null) {
            return node;
        }
        // node 如果有右孩子，后继节点为右孩子的最左节点
        if (node.right != null) {
            return getLeftMost(node.right);
        } else {
            // node 如果没有右孩子，往上找，如果为一个节点的左孩子时，这个节点为后继节点
            TreeNode p = node.parent;
            while (p != null) {
                if (node == p.left) {
                    return p;
                }
                node = p;
                p = p.parent;
            }
        }
        // 如果找到根节点了 还没有这样的节点，那这个节点没有后继节点
        return null;
}

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

4. 折纸问题

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

例如：N=1时，打印： down；N=2时，打印： down down up

5. 介绍二叉树的序列化和反序列化

序列化 (Serialization)是将对象的状态信息转换为可以存储或传输的形式的过程。在序列化期间，对象将其当前状态写入到临时或持久性存储区。以后，可以通过从存储区中读取或反序列化对象的状态，重新创建该对象。

序列化可以使用先序遍历、中序遍历或者层次遍历实现。需要注意一下两点：

  • 空节点要使用占位符：否则节点数据值一致且数量相同时无法还原结构
  • 节点与节点之间要使用分隔符：为了区分不同节点的数据值
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 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<>();
   for (int i = 0; i != values.length; i++) {
      queue.offer(values[i]);
   }
   return reconPreOrder(queue);
}

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

6. 判断一棵二叉树是否是平衡二叉树

平衡二叉树：对于一棵二叉树上的任意一个节点，左右子树的高度差不超过 1

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
 
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 isBalance2(Node head) {
   return process(head).isB;
}

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

7. 判断一棵树是否是搜索二叉树、判断一棵树是否是完全二叉树

搜索二叉树：对于一棵二叉树上的任何一个节点，该节点的左孩子 < 该节点 < 该节点的右孩子。

通常来讲，搜索二叉树是不含有重复节点的，相同的节点值会压缩到一个节点中。

由定义可知，二叉树的中序遍历是升序的。

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
 
public static boolean isBST(Node head) {
   if (head == null) {
      return false;
   }
   int minNum = Integer.MIN_VALUE;
   int cur;
   Stack<Node> stack = new Stack<>();
   while (!stack.isEmpty() || head != null) {
      if (head != null) {
         stack.push(head);
         head = head.left;
      }
      head = stack.pop();
      // 判断逻辑：不符合升序返回 false
      cur = head.value;
      if (cur < minNum) return false;
      minNum = cur;
      head = head.right;
   }
   return true;
}

public static boolean isCBT(Node head) {
     if (head == null) {
            return false;
      }
        Queue<Node> queue = new LinkedList<>();
     queue.add(head);
     boolean leaf = false;
      Node l;
      Node r;
      
        * 1. 有右无左：false
         * 2. 有左无右 无左无右：按层次遍历，后边全部为叶节点时为 true
        * 3. 有左有右
       */
       while (!queue.isEmpty()) {
          head = queue.poll();
         l = head.left;
           r = head.right;
          if ((leaf == true && (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;
}

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

要求：时间复杂度低于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
 
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) {
 // 到底，以叶节点为头的完全二叉树节点个数为 1
   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++;
     node = node.left;
    }
    return level - 1;
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能