Tree 树结构

红太狼 2024-03-17 13:47 58阅读 0赞

**Case 1st** 最少的摄像头——亚马逊面试问题

给定一个二叉树，我们在树的节点上安装摄像头。

节点上的每个摄像机都可以监视其父级、自身及其直接子级。

计算监视树的所有节点所需的最小摄像机数。

![alt][]

例：

Input: [0,0,null,0,0]
    Output: 1
    Explanation: One camera is enough to monitor all nodes if placed as shown.

了解问题：

由于我们希望尽量减少相机的数量，因此有一点很清楚，我们不会将相机放置在叶节点上。

所以我们可以从叶子到根追溯。这使得DFS成为解决问题的最可能选择。

但是当我们回溯时，我们需要在节点之间交换信息，以查看当前节点是否需要摄像头。

如果上一个节点已经有摄像头，我们不需要摄像头。总而言之，我们需要考虑以下事项：

如果当前节点是叶节点，则我们不需要相机。

如果我们在当前节点上没有摄像头，那么父节点需要它。

如果当前节点具有相机，则其父节点不需要相机。

我们可以分配不同的值来指示这些状态。-1 从孩子的意思是放相机。1 来自任何孩子意味着没有相机。

代码实现：

# Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    class Solution:
        def minCameraCover(self, root: TreeNode) -> int:
            def dfs(node):
                l=0
                r=0
                if (node.left is None and node.right is None):
                    return -1
                if node.left:
                    l = dfs(node.left)
                if node.right:
                    r = dfs(node.right)
                if(l == -1 or r == -1):
                    self.count += 1
                    return 1
                if(l == 0 and r == 0):
                    return -1
                if(l == 1 or r == 1):
                    return 0
            self.count=0
            cams = dfs(root)
            if(cams == -1):
                self.count += 1
            return self.count

复杂性分析

时间复杂度：O（N），其中 N 是二叉树中的节点数

空间复杂性：递归调用堆栈的空间，可能是 N

**Case 2nd** 族谱

了解到家族成员的代际关系，我们想透过图的关系信息输入，返回任意某人是第几代？

英伟达和AMD之间是否存在完全竞争？下图显示了黄仁勋和苏丽莎家谱显示他们的关系有多密切？

![alt][alt 1]

如何构造恰当的数据结构？

1、构造家庭成员的class类 `FamilyMember`

2、追加家庭成员的profile信息对应到树连接节点

3、如何输出打印

class类 `FamilyMember`

class FamilyMember:
    
        def __init__(self, name, gender, generation):
            self.name = name
            self.gender = gender
            self.generation = generation
            self.children = []
            self.parents = []
    
    
    # 家族根
    root = FamilyMember("John", "Male", 0)
    
    # John 的子女
    child1 = FamilyMember("Jane", "Female", 1)
    child2 = FamilyMember("Mike", "Male", 1)
    root.children.append(child1)
    root.children.append(child2)
    child1.parents.append(root)
    child2.parents.append(root)
    
    #  Jane 和 Mike 的子女
    grandchild1 = FamilyMember("Jay", "Male", 2)
    grandchild2 = FamilyMember("Joy", "Female", 2)
    ...
    child1.children.append(grandchild1)
    child1.children.append(grandchild2)
    grandchild1.parents.append(child1)
    ...

输出：

#递归
    def print_family(member):
        print(f"{member.name} - {member.gender} - Generation {member.generation}")
        for child in member.children:
            print(" |--", end="") 
            print_family(child)
            
    print_family(root)

2.如何打印输出直观效果的家族树？

我们定义了一个print\_family()函数,它能递归地打印指定家庭成员以及其子节点。

通过在每个节点前增加 "| "符号,就能形成一个漂亮的树形结构。 关键点是:

1.  递归调用print\_family(),打印每个子节点；
2.  在子节点前增加 "|" 和"--"符号,形成一个缩进结构；
3.  打印每个节点的时候,打印其名称、性别和代数信息；

执行print\_family(root),就可以打印出整个家族结构。 可以看到,使用递归,就可以很简单地打印出一个复杂的树形结构。 你可能还想添加更多功能,比如:

*  查找指定成员
 *  计算指定成员的后代数
 *  统计各代人口数
 *  画出家族结构图

这些都可以基于上述基本功能来实现。 通过分解为类、方法和函数,编码家族结构会更加模块化和可扩展。

John - Male - Generation 0
     |--Jane - Female - Generation 1
     |--Jay - Male - Generation 2
     |--Joy - Female - Generation 2
     |--Mike - Male - Generation 1

当我们想了解某个家族成员处于族谱中的第几代，如何构造算法？

def count_gen(Familytree, person):
        prev = set()
        for r in Familytree:
            while r not in prev:
                prev.add(r)
                r = tree[r]
        return len(skils)

致所有受到时间约束的工程师的任务清单

对于那些正在找工作的时间有限的工程师,这里有一份列出各类型问题中最好的LeetCode题目的列表,它可以教你每个类别/类型问题的核心概念和技巧!

许多其他LeetCode题目都是这些个别题目技巧的混合。 在我上一个求职过程中,我使用这个列表只做重要的题目。

如下:

•Arrays - Two Sum
    •Strings - Longest Substring Without Repeating Characters
    •Linked Lists - Reverse a Linked List
    •Stacks - Validate Stack Sequences
    •Queues - Implement Queue using Stacks
    •Trees - Binary Tree Inorder Traversal
    •Binary Search - Search Insert Position
    •Sorting - Merge Sort
    •Hash Tables - Two Sum
    •Dynamic Programming - Climbing Stairs
    •Greedy Algorithms - Maximum Units on a Truck
    •Depth First Search - Number of Islands
    •Breadth First Search - Clone Graph
    •Bit Manipulation - Single Number
    •Backtracking - Permutations
    •Sliding Window - Maximum Sum Subarray of Size K
    •Divide and Conquer - Merge Sorted Array
    •Recursion - Reverse a String
    •Binary Search Tree - Lowest Common Ancestor of a Binary Tree
    •Heaps - Merge K Sorted Lists
    •Trie - Implement Trie (Prefix Tree) （

Array

*  Two Sum - https://leetcode.com/problems/two-sum/
 *  Best Time to Buy and Sell Stock - https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
 *  Contains Duplicate - https://leetcode.com/problems/contains-duplicate/
 *  Product of Array Except Self - https://leetcode.com/problems/product-of-array-except-self/
 *  Maximum Subarray - https://leetcode.com/problems/maximum-subarray/
 *  Maximum Product Subarray - https://leetcode.com/problems/maximum-product-subarray/
 *  Find Minimum in Rotated Sorted Array - https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
 *  Search in Rotated Sorted Array - https://leetcode.com/problems/search-in-rotated-sorted-array/
 *  3Sum - https://leetcode.com/problems/3sum/
 *  Container With Most Water - https://leetcode.com/problems/container-with-most-water/

--------------------

Binary

*  Sum of Two Integers - https://leetcode.com/problems/sum-of-two-integers/
 *  Number of 1 Bits - https://leetcode.com/problems/number-of-1-bits/
 *  Counting Bits - https://leetcode.com/problems/counting-bits/
 *  Missing Number - https://leetcode.com/problems/missing-number/
 *  Reverse Bits - https://leetcode.com/problems/reverse-bits/

--------------------

Dynamic Programming

*  Climbing Stairs - https://leetcode.com/problems/climbing-stairs/
 *  Coin Change - https://leetcode.com/problems/coin-change/
 *  Longest Increasing Subsequence - https://leetcode.com/problems/longest-increasing-subsequence/
 *  Longest Common Subsequence -
 *  Word Break Problem - https://leetcode.com/problems/word-break/
 *  Combination Sum - https://leetcode.com/problems/combination-sum-iv/
 *  House Robber - https://leetcode.com/problems/house-robber/
 *  House Robber II - https://leetcode.com/problems/house-robber-ii/
 *  Decode Ways - https://leetcode.com/problems/decode-ways/
 *  Unique Paths - https://leetcode.com/problems/unique-paths/
 *  Jump Game - https://leetcode.com/problems/jump-game/

--------------------

Graph

*  Clone Graph - https://leetcode.com/problems/clone-graph/
 *  Course Schedule - https://leetcode.com/problems/course-schedule/
 *  Pacific Atlantic Water Flow - https://leetcode.com/problems/pacific-atlantic-water-flow/
 *  Number of Islands - https://leetcode.com/problems/number-of-islands/
 *  Longest Consecutive Sequence - https://leetcode.com/problems/longest-consecutive-sequence/
 *  Alien Dictionary (Leetcode Premium) - https://leetcode.com/problems/alien-dictionary/
 *  Graph Valid Tree (Leetcode Premium) - https://leetcode.com/problems/graph-valid-tree/
 *  Number of Connected Components in an Undirected Graph (Leetcode Premium) - https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/

--------------------

Interval

*  Insert Interval - https://leetcode.com/problems/insert-interval/
 *  Merge Intervals - https://leetcode.com/problems/merge-intervals/
 *  Non-overlapping Intervals - https://leetcode.com/problems/non-overlapping-intervals/
 *  Meeting Rooms (Leetcode Premium) - https://leetcode.com/problems/meeting-rooms/
 *  Meeting Rooms II (Leetcode Premium) - https://leetcode.com/problems/meeting-rooms-ii/

--------------------

Linked List

*  Reverse a Linked List - https://leetcode.com/problems/reverse-linked-list/
 *  Detect Cycle in a Linked List - https://leetcode.com/problems/linked-list-cycle/
 *  Merge Two Sorted Lists - https://leetcode.com/problems/merge-two-sorted-lists/
 *  Merge K Sorted Lists - https://leetcode.com/problems/merge-k-sorted-lists/
 *  Remove Nth Node From End Of List - https://leetcode.com/problems/remove-nth-node-from-end-of-list/
 *  Reorder List - https://leetcode.com/problems/reorder-list/

--------------------

Matrix

*  Set Matrix Zeroes - https://leetcode.com/problems/set-matrix-zeroes/
 *  Spiral Matrix - https://leetcode.com/problems/spiral-matrix/
 *  Rotate Image - https://leetcode.com/problems/rotate-image/
 *  Word Search - https://leetcode.com/problems/word-search/

--------------------

String

*  Longest Substring Without Repeating Characters - https://leetcode.com/problems/longest-substring-without-repeating-characters/
 *  Longest Repeating Character Replacement - https://leetcode.com/problems/longest-repeating-character-replacement/
 *  Minimum Window Substring - https://leetcode.com/problems/minimum-window-substring/
 *  Valid Anagram - https://leetcode.com/problems/valid-anagram/
 *  Group Anagrams - https://leetcode.com/problems/group-anagrams/
 *  Valid Parentheses - https://leetcode.com/problems/valid-parentheses/
 *  Valid Palindrome - https://leetcode.com/problems/valid-palindrome/
 *  Longest Palindromic Substring - https://leetcode.com/problems/longest-palindromic-substring/
 *  Palindromic Substrings - https://leetcode.com/problems/palindromic-substrings/
 *  Encode and Decode Strings (Leetcode Premium) - https://leetcode.com/problems/encode-and-decode-strings/

--------------------

Tree

*  Maximum Depth of Binary Tree - https://leetcode.com/problems/maximum-depth-of-binary-tree/
 *  Same Tree - https://leetcode.com/problems/same-tree/
 *  Invert/Flip Binary Tree - https://leetcode.com/problems/invert-binary-tree/
 *  Binary Tree Maximum Path Sum - https://leetcode.com/problems/binary-tree-maximum-path-sum/
 *  Binary Tree Level Order Traversal - https://leetcode.com/problems/binary-tree-level-order-traversal/
 *  Serialize and Deserialize Binary Tree - https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
 *  Subtree of Another Tree - https://leetcode.com/problems/subtree-of-another-tree/
 *  Construct Binary Tree from Preorder and Inorder Traversal - https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
 *  Validate Binary Search Tree - https://leetcode.com/problems/validate-binary-search-tree/
 *  Kth Smallest Element in a BST - https://leetcode.com/problems/kth-smallest-element-in-a-bst/
 *  Lowest Common Ancestor of BST - https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
 *  Implement Trie (Prefix Tree) - https://leetcode.com/problems/implement-trie-prefix-tree/
 *  Add and Search Word - https://leetcode.com/problems/add-and-search-word-data-structure-design/
 *  Word Search II - https://leetcode.com/problems/word-search-ii/

--------------------

Heap

*  Merge K Sorted Lists - https://leetcode.com/problems/merge-k-sorted-lists/
 *  Top K Frequent Elements - https://leetcode.com/problems/top-k-frequent-elements/
 *  Find Median from Data Stream - https://leetcode.com/problems/find-median-from-data-stream/

二叉搜索树是如何实现的？（解决方案)

如何在给定的二叉树中执行预序遍历？（解决方案)

如何在没有递归的情况下以预序遍历给定的二叉树？（解决方案)

如何在给定的二叉树中执行无序遍历？（解决方案)

如何使用无序遍历打印给定二叉树的所有节点而不递归？（解决方案)

如何实现后序遍历算法？（解决方案)

如何在没有递归的情况下在后序遍历中遍历二叉树？（解决方案)

二叉搜索树的所有叶子是如何打印的？（解决方案)

你如何计算给定二叉树中的叶节点数？（解决方案)

如何在给定数组中执行二叉搜索？（解决方案)

如何在 Java 中将给定的二叉树转换为双链表？（解决方案）

编写一个程序来查找 Java 中给定二叉树的深度？（解决方案）

二叉搜索树和二叉搜索树有什么区别？（答案）

什么是自平衡树？（答案）

什么是 AVL 树？（答案）

您给出了一个 BST，其中交换了两个节点？你如何恢复原始的BST？（解决方案）

如何在 Java 中将二叉树转换为二叉搜索树？（解决方案)

在 Java 中找到给定二叉树的最大 BST 子树？（解决方案）

编写一个 Java 程序来连接与二叉树相同级别的节点？（解决方案）

什么是 Trie 数据结构？（答案）

二叉树和Trie有什么区别？（答案）

如何检查给定的二叉树是否是BST？（解决方案)

如何计算给定二叉树中的叶节点数（解决方案)

如何在 Java 中打印给定二叉树的叶节点？（解决方案)

如何检查二叉树中是否存在给定节点？（解决方案)

如何在二叉搜索树中找到第 K 个最小元素？（解决方案)

如何在给定的二叉树中找到最大总和水平？（解决方案)

如何在爪哇中找到二叉树的最低共同祖先？（解决方案)

https://www.alivegarden.com/

本文由[ mdnice ][mdnice]多平台发布

[alt]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/acda8c69c4934d06a7b9fb352d54cb3d.png
[alt 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/cae6411dd70d411dbdc7803418e3a50b.png
[mdnice]: https://mdnice.com/?platform=4