LeeCode中如何定义常见的数据结构？

系统管理员 2022-12-08 01:55 113阅读 0赞

# 1. 单链表： #

## 1.1 单链表结点： ##

// Definition for singly-linked list.
    public static class ListNode { 
        int val;
        ListNode next;
    
        ListNode(int x) { 
            val = x;
        }
    }

## 1.2 构建单链表： ##

### 1.2.1 ListNodeUtil类： ###

public static class ListNodeUtil { 
    
        // 构建链表
        public static ListNode createLinkedList(int[] arr) {  // 将输入的数组输入到链表中
            if (arr.length == 0) { 
                return null;
            }
            ListNode head = new ListNode(arr[0]);
            ListNode current = head;
            for (int i = 1; i < arr.length; i++) { // 过程
                current.next = new ListNode(arr[i]);
                current = current.next;
            }
            return head;
        }
    
        // 打印链表
        public static void printLinkedList(ListNode head) {  // 将链表结果打印
            ListNode current = head;
            while (current != null) { 
                System.out.printf("%d -> ", current.val);
                current = current.next;
            }
            System.out.println("NULL");
        }
    }

### 1.2.2 Main类： ###

import java.util.*;
    
    public class Main { 
    
        public static void main(String[] args) { 
            int[] x = { 1, 2, 3, 4, 5, 6};
            ListNode list = ListNodeUtil.createLinkedList(x);
            ListNodeUtil.printLinkedList(list);
        }
    }

# 2. 二叉树： #

## 2.1 二叉树结点： ##

// Definition for a binary tree node.
    public static class TreeNode { 
        int val;
        TreeNode left;
        TreeNode right;
    
        TreeNode(int x) { 
            val = x;
        }
    }

## 2.2 构建二叉树： ##

### 2.2.1 TreeNodeUtil类： ###

import java.util.*;
    
    public static class TreeNodeUtil { 
        public static TreeNode arrayToTreeNode(Integer[] array) { 
            if (array.length == 0) { 
                return null;
            }
            TreeNode root = new TreeNode(array[0]);
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            boolean isLeft = true;
            for (int i = 1; i < array.length; i++) { 
                TreeNode node = queue.peek();
                if (isLeft) { 
                    if (array[i] != null) { 
                        node.left = new TreeNode(array[i]);
                        queue.offer(node.left);
                    }
                    isLeft = false;
                } else { 
                    if (array[i] != null) { 
                        node.right = new TreeNode(array[i]);
                        queue.offer(node.right);
                    }
                    queue.poll();
                    isLeft = true;
                }
            }
            return root;
        }
    }

### 2.2.2 Main类： ###

import java.util.*;
    
    public class Main { 
    
        public static void main(String[] args) { 
            Integer nums[] = { 5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1};
    
            // 构造树的方法:
            TreeNode tree = TreeNodeUtil.arrayToTreeNode(nums);
            TreeOperation.show(tree);
        }
    }

# 参考： #

1.  [LeetCode如何构建链表和树的测试用例][LeetCode]
2.  [Java一维数组转换二叉树结构][Java]
3.  [Java 一维数组转换二叉树][Java 1]
4.  [Java一维数组转换二叉树结构][Java 2]

[LeetCode]: https://blog.csdn.net/zyx_ly/article/details/104319295
[Java]: https://www.cnblogs.com/ghimtim/p/12905792.html
[Java 1]: https://leetcode-cn.com/circle/article/htJ97s/
[Java 2]: http://www.manongjc.com/detail/16-hqyqmnjfnipljri.html