devbox
Monodyee
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

算法体系-12 第 十二 二叉树的基本算法 下

作者：Monodyee | 2024-03-24 08:30:12

赞

踩

算法体系-12 第 十二 二叉树的基本算法 下

一 实现二叉树的按层遍历

1.1 描述

1）其实就是宽度优先遍历，用队列

2）可以通过设置flag变量的方式，来发现某一层的结束（看题目）看下边的第四题解答

1.2 代码

  1. public class Code01_LevelTraversalBT {
  2.  
  3.     public static class Node {
  4.         public int value;
  5.         public Node left;
  6.         public Node right;
  7.  
  8.         public Node(int v) {
  9.             value = v;
  10.         }
  11.     }
  12.  
  13.     public static void level(Node head) {
  14.         if (head == null) {
  15.             return;
  16.         }
  17.         Queue<Node> queue = new LinkedList<>();
  18.         queue.add(head);
  19.         while (!queue.isEmpty()) {
  20.             Node cur = queue.poll();
  21.             System.out.println(cur.value);
  22.             if (cur.left != null) {
  23.                 queue.add(cur.left);
  24.             }
  25.             if (cur.right != null) {
  26.                 queue.add(cur.right);
  27.             }
  28.         }
  29.     }

二 实现二叉树的序列化和反序列化

2.1描述

1）先序方式序列化和反序列化

2）按层方式序列化和反序列化

将二叉树序力化为唯一的字符串叫序力化，字符串也能转出唯一的数二叉树叫反序力化

2.2 分析

2.3 前序列化代码

  1. public static class Node {
  2.         public int value;
  3.         public Node left;
  4.         public Node right;
  5.  
  6.         public Node(int data) {
  7.             this.value = data;
  8.         }
  9.     }
  10.  
  11.     public static Queue<String> preSerial(Node head) {
  12.         Queue<String> ans = new LinkedList<>();
  13.         pres(head, ans);
  14.         return ans;
  15.     }
  16.  
  17.     public static void pres(Node head, Queue<String> ans) {
  18.         if (head == null) {
  19.             ans.add(null);
  20.         } else {
  21.             ans.add(String.valueOf(head.value));
  22.             pres(head.left, ans);
  23.             pres(head.right, ans);
  24.         }
  25.     }

2.4 前序反序列化

  1. public static Node buildByPreQueue(Queue<String> prelist) {
  2.         if (prelist == null || prelist.size() == 0) {
  3.             return null;
  4.         }
  5.         return preb(prelist);
  6.     }
  7.  
  8.     public static Node preb(Queue<String> prelist) {
  9.         String value = prelist.poll();
  10.         if (value == null) {
  11.             return null;
  12.         }
  13.         Node head = new Node(Integer.valueOf(value));
  14.         head.left = preb(prelist);
  15.         head.right = preb(prelist);
  16.         return head;
  17.     }

2.5 中序列化代码

由上图可以知道，中序序例化是有歧义的，所以不存在中序的序列化

  1. public static Queue<String> inSerial(Node head) {
  2.         Queue<String> ans = new LinkedList<>();
  3.         ins(head, ans);
  4.         return ans;
  5.     }
  6.  
  7.     public static void ins(Node head, Queue<String> ans) {
  8.         if (head == null) {
  9.             ans.add(null);
  10.         } else {
  11.             ins(head.left, ans);
  12.             ans.add(String.valueOf(head.value));
  13.             ins(head.right, ans);
  14.         }
  15.     }

2.7 中序反列化 

2.8 后序列化代码

  1. public static Queue<String> posSerial(Node head) {
  2.         Queue<String> ans = new LinkedList<>();
  3.         poss(head, ans);
  4.         return ans;
  5.     }
  6.  
  7.     public static void poss(Node head, Queue<String> ans) {
  8.         if (head == null) {
  9.             ans.add(null);
  10.         } else {
  11.             poss(head.left, ans);
  12.             poss(head.right, ans);
  13.             ans.add(String.valueOf(head.value));
  14.         }
  15.     }

2.9后序反列化代码

  1. public static Node buildByPosQueue(Queue<String> poslist) {
  2.         if (poslist == null || poslist.size() == 0) {
  3.             return null;
  4.         }
  5.         // 左右中  ->  stack(中右左) 默认是左右中，这种情况没法首先没法建立头节点，因此进行转化为头在前面的情况，把它放入stack(中右左)，这是头就先出来，就可以新建head
  6.         Stack<String> stack = new Stack<>();
  7.         while (!poslist.isEmpty()) {
  8.             stack.push(poslist.poll());
  9.         }
  10.         return posb(stack);
  11.     }
  12.  
  13.     public static Node posb(Stack<String> posstack) {
  14.         String value = posstack.pop();
  15.         if (value == null) {
  16.             return null;
  17.         }
  18.         Node head = new Node(Integer.valueOf(value));
  19.         head.right = posb(posstack);
  20.         head.left = posb(posstack);
  21.         return head;
  22.     }

3.0 按层序列化和反序列化

3.0.1分析

3.0.2 按层序列化 代码

  1. public static Queue<String> levelSerial(Node head) {
  2.         Queue<String> ans = new LinkedList<>();
  3.         if (head == null) {
  4.             ans.add(null);
  5.         } else {
  6.             ans.add(String.valueOf(head.value));
  7.             Queue<Node> queue = new LinkedList<Node>();
  8.             queue.add(head);
  9.             while (!queue.isEmpty()) {
  10.                 head = queue.poll(); // head 父   子
  11.                 if (head.left != null) {
  12.                     ans.add(String.valueOf(head.left.value));
  13.                     queue.add(head.left);
  14.                 } else {
  15.                     ans.add(null);
  16.                 }
  17.                 if (head.right != null) {
  18.                     ans.add(String.valueOf(head.right.value));
  19.                     queue.add(head.right);
  20.                 } else {
  21.                     ans.add(null);
  22.                 }
  23.             }
  24.         }
  25.         return ans;
  26.     }

3.0.3 按层反序列化 代码

  1.  
  2.     public static Node buildByLevelQueue(Queue<String> levelList) {
  3.         if (levelList == null || levelList.size() == 0) {
  4.             return null;
  5.         }
  6.         Node head = generateNode(levelList.poll());
  7.         Queue<Node> queue = new LinkedList<Node>();
  8.         if (head != null) {
  9.             queue.add(head);
  10.         }
  11.   //因为要记录上一次的节点，这里借用队列来完成
  12.         Node node = null;
  13.         while (!queue.isEmpty()) {
  14.             node = queue.poll();
  15.             node.left = generateNode(levelList.poll());
  16.             node.right = generateNode(levelList.poll());
  17.             if (node.left != null) {
  18.                 queue.add(node.left);
  19.             }
  20.             if (node.right != null) {
  21.                 queue.add(node.right);
  22.             }
  23.         }
  24.         return head;
  25.     }
  26.  
  27.     public static Node generateNode(String val) {
  28.         if (val == null) {
  29.             return null;
  30.         }
  31.         return new Node(Integer.valueOf(val));
  32.     }

三 Encode N-ary Tree to Binary Tree

3.1 描述

一颗多叉树，序历化为为二叉树，二叉树也能转为原来的多叉树；

3.2 分析

第一步 先将多叉树的每个节点的孩子放在对应节点左树的右边界上；

左树的节点为该节点的第一个树，反回来看某个节点是否有孩子看该节点左数是否有右边孩子

结构如下

3.3 代码

  1. package class11;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.List;
  5.  
  6. // 本题测试链接：https://leetcode.com/problems/encode-n-ary-tree-to-binary-tree
  7. public class Code03_EncodeNaryTreeToBinaryTree {
  8.  
  9.     // 提交时不要提交这个类
  10.     public static class Node {
  11.         public int val;
  12.         public List<Node> children;
  13.  
  14.         public Node() {
  15.         }
  16.  
  17.         public Node(int _val) {
  18.             val = _val;
  19.         }
  20.  
  21.         public Node(int _val, List<Node> _children) {
  22.             val = _val;
  23.             children = _children;
  24.         }
  25.     };
  26.  
  27.     // 提交时不要提交这个类
  28.     public static class TreeNode {
  29.         int val;
  30.         TreeNode left;
  31.         TreeNode right;
  32.  
  33.         TreeNode(int x) {
  34.             val = x;
  35.         }
  36.     }
  37.  
  38.     // 只提交这个类即可
  39.     class Codec {
  40.         // Encodes an n-ary tree to a binary tree.
  41.         public TreeNode encode(Node root) {
  42.             if (root == null) {
  43.                 return null;
  44.             }
  45.             TreeNode head = new TreeNode(root.val);
  46.             head.left = en(root.children);
  47.             return head;
  48.         }
  49.  
  50.         private TreeNode en(List<Node> children) {
  51.             TreeNode head = null;
  52.             TreeNode cur = null;
  53.             for (Node child : children) {
  54.                 TreeNode tNode = new TreeNode(child.val);
  55.                 if (head == null) {
  56.                     head = tNode;
  57.                 } else {
  58.                     cur.right = tNode;
  59.                 }
  60.                 cur = tNode;
  61.                 cur.left = en(child.children);
  62.             }
  63.             return head;
  64.         }
  65.  
  66.         // Decodes your binary tree to an n-ary tree.
  67.         public Node decode(TreeNode root) {
  68.             if (root == null) {
  69.                 return null;
  70.             }
  71.             return new Node(root.val, de(root.left));
  72.         }
  73.  
  74.         public List<Node> de(TreeNode root) {
  75.             List<Node> children = new ArrayList<>();
  76.             while (root != null) {
  77.                 Node cur = new Node(root.val, de(root.left));
  78.                 children.add(cur);
  79.                 root = root.right;
  80.             }
  81.             return children;
  82.         }
  83.  
  84.     }
  85.  
  86. }

四 求二叉树最宽的层有多少个节点

4.1 描述

打印二叉树每层的的节点树及最多的节点数；

4.2 分析

根据宽度优先遍历的基础上，要是能知道哪一层结束，那么就能算出每一层的节点数；

设计两个数，Node curEnd = head; // 当前层，最右节点是谁Node nextEnd = null; // 下一层，最右节点是谁

每次遍历当前节点时候，判断该节点是否和记录的curEnd节点相等，相等就是当前层结束了，把当前层的节点数更新到max中，

再将当前节点的每一个左右孩子更新到队列中的过程中，每一步都更新nextEnd的值为当前加队列的值，下一层遍历来的时候更新curEnd值为nextEnd

4.3 代码

  1. public static int maxWidthNoMap(Node head) {
  2.         if (head == null) {
  3.             return 0;
  4.         }
  5.         Queue<Node> queue = new LinkedList<>();
  6.         queue.add(head);
  7.         Node curEnd = head; // 当前层，最右节点是谁
  8.         Node nextEnd = null; // 下一层的最右节点是谁。提前为下一层出来的end节点做准备
  9.         int max = 0;
  10.         int curLevelNodes = 0; // 当前层的节点数
  11.         while (!queue.isEmpty()) {
  12.             Node cur = queue.poll();
  13.             if (cur.left != null) {
  14.                 queue.add(cur.left);
  15.                 nextEnd = cur.left;
  16.             }
  17.             if (cur.right != null) {
  18.                 queue.add(cur.right);
  19.                 nextEnd = cur.right;
  20.             }
  21.             curLevelNodes++;
  22.             if (cur == curEnd) {
  23.                 max = Math.max(max, curLevelNodes);
  24.                 curLevelNodes = 0;
  25.                 curEnd = nextEnd;
  26.             }
  27.         }
  28.         return max;
  29.     }
  30.  
  31.  
  32.  
  33.  //使用额外HashMapd
  34.  public static class Node {
  35.         public int value;
  36.         public Node left;
  37.         public Node right;
  38.  
  39.         public Node(int data) {
  40.             this.value = data;
  41.         }
  42.     }
  43.  
  44.     public static int maxWidthUseMap(Node head) {
  45.         if (head == null) {
  46.             return 0;
  47.         }
  48.         Queue<Node> queue = new LinkedList<>();
  49.         queue.add(head);
  50.         // key 在 哪一层，value
  51.         HashMap<Node, Integer> levelMap = new HashMap<>();
  52.         levelMap.put(head, 1);
  53.         int curLevel = 1; // 当前你正在统计哪一层的宽度
  54.         int curLevelNodes = 0; // 当前层curLevel层，宽度目前是多少
  55.         int max = 0;
  56.         while (!queue.isEmpty()) {
  57.             Node cur = queue.poll();
  58.             int curNodeLevel = levelMap.get(cur);
  59.             if (cur.left != null) {
  60.                 levelMap.put(cur.left, curNodeLevel + 1);
  61.                 queue.add(cur.left);
  62.             }
  63.             if (cur.right != null) {
  64.                 levelMap.put(cur.right, curNodeLevel + 1);
  65.                 queue.add(cur.right);
  66.             }
  67.             if (curNodeLevel == curLevel) {
  68.                 curLevelNodes++;
  69.             } else {
  70.                 max = Math.max(max, curLevelNodes);
  71.                 curLevel++;
  72.                 curLevelNodes = 1;
  73.             }
  74.         }
  75.         max = Math.max(max, curLevelNodes);
  76.         return max;
  77.     }

五 二叉树中的某个节点，返回该节点的后继节点

5.1 描述

后继节点 ：比如中序遍历，求该节点的4的后继节点，就是中序遍历遍历到该节点后的所有节点

二叉树结构如下定义：

Class Node {

V value;

Node left;

Node right;

Node parent;

}

给你二叉树中的某个节点，返回该节点的后继节点

5.2 分析 中序遍历

5.2.1 方案一 先通过parrent 找到的他的跟节点后，然后通root找到他的中序遍历，然后就可以找到该节点的后继节点

方案二

5.2.2 情况1一 如果该节点有右数，那么他的后继节点一定是他右树的最左侧节点

情况二 当该节点没有右树的时候，去找该节点是谁的节点左树的最右侧节点（中序遍历的本质理解）如果没有右子树，根据中序遍历的特点，下一个就应该是去找该节点是谁的节点左树的最右侧节点

情况二 讨论如下 找一个数的后继节点，一直往上找，通过找到该节点的最后一个父节点，该节点的右子树就是他的后继节点

如下，x是y左数的最右节点，所以打印完x就该打印y了 == 找的就是那个左树上的最右节点

5.3 代码

  1. public class Code06_SuccessorNode {
  2.  
  3.     public static class Node {
  4.         public int value;
  5.         public Node left;
  6.         public Node right;
  7.         public Node parent;
  8.  
  9.         public Node(int data) {
  10.             this.value = data;
  11.         }
  12.     }
  13.  
  14.     public static Node getSuccessorNode(Node node) {
  15.         if (node == null) {
  16.             return node;
  17.         }
  18.         if (node.right != null) {
  19.             return getLeftMost(node.right);
  20.         } else { // 无右子树
  21.             Node parent = node.parent;
  22.             while (parent != null && parent.right == node) { // 当前节点是其父亲节点右孩子
  23.                 node = parent;
  24.                 parent = node.parent;
  25.             }
  26.             return parent;
  27.         }
  28.     }
  29.  
  30.     public static Node getLeftMost(Node node) {
  31.         if (node == null) {
  32.             return node;
  33.         }
  34.         while (node.left != null) {
  35.             node = node.left;
  36.         }
  37.         return node;
  38.     }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/301071
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号