• 算法体系-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 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 preSerial(Node head) {
    12.         Queue ans = new LinkedList<>();
    13.         pres(head, ans);
    14.         return ans;
    15.     }
    16.  
    17.     public static void pres(Node head, Queue 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 prelist) {
    2.         if (prelist == null || prelist.size() == 0) {
    3.             return null;
    4.         }
    5.         return preb(prelist);
    6.     }
    7.  
    8.     public static Node preb(Queue 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 inSerial(Node head) {
    2.         Queue ans = new LinkedList<>();
    3.         ins(head, ans);
    4.         return ans;
    5.     }
    6.  
    7.     public static void ins(Node head, Queue 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 posSerial(Node head) {
    2.         Queue ans = new LinkedList<>();
    3.         poss(head, ans);
    4.         return ans;
    5.     }
    6.  
    7.     public static void poss(Node head, Queue 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 poslist) {
    2.         if (poslist == null || poslist.size() == 0) {
    3.             return null;
    4.         }
    5.         // 左右中  ->  stack(中右左) 默认是左右中，这种情况没法首先没法建立头节点，因此进行转化为头在前面的情况，把它放入stack(中右左)，这是头就先出来，就可以新建head
    6.         Stack 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 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 levelSerial(Node head) {
    2.         Queue ans = new LinkedList<>();
    3.         if (head == null) {
    4.             ans.add(null);
    5.         } else {
    6.             ans.add(String.valueOf(head.value));
    7.             Queue queue = new LinkedList();
    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 levelList) {
    3.         if (levelList == null || levelList.size() == 0) {
    4.             return null;
    5.         }
    6.         Node head = generateNode(levelList.poll());
    7.         Queue queue = new LinkedList();
    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 children;
    13.  
    14.         public Node() {
    15.         }
    16.  
    17.         public Node(int _val) {
    18.             val = _val;
    19.         }
    20.  
    21.         public Node(int _val, List _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 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 de(TreeNode root) {
    75.             List 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 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 queue = new LinkedList<>();
    49.         queue.add(head);
    50.         // key 在 哪一层，value
    51.         HashMap 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.     }

  • 相关阅读:
    从零开始学React--环境搭建
    C++ 字符串
    （51单片机）第十一章-串行口应用提高
    CentOS 配置 sftp 服务
    2.1.2 运算放大器的组成与分类、运算放大器的发展历程
    低代码掀起“数字革命”，引领制造业数字化转型
    开发工具篇第七讲：阿里云日志查询与分析
    【Azure Developer】Azure AD 注册应用的 OAuth 2.0 v2 终结点获取的 Token 解析出来依旧为v1， 这是什么情况！
    uniapp 小程序 父组件调用子组件方法
    《Effective C++》条款12
  • 原文地址：https://blog.csdn.net/m0_61164038/article/details/136857904