Tuần này, mình thuộc giải tiếp một bài xích leetcode về binary tree, 94. Binary Tree Inorder Traversal

Đề bài

Given the root of a binary tree, return the inorder traversal of its nodes’ values.

Bạn đang xem: Bố là tất cả

Ví dụ 1

Input: root = <1,null,2,3>Output: <1,3,2>Ví dụ 2

Input: root = <1,null,2>Output: <1,2>(bạn hãy tham khảo đề vào leetcode để có mô tả thêm về hình hình ảnh nhé)

Phân tích đề

Đề tài yêu mong mình vẫn nhận một cây nhị phân, rồi trả về quý hiếm của nút theo thứ tự xem xét là inorder traversal.

Cây nhị phân

Cây nhị phân(binary tree) là một cấu trúc dữ liệu dạng cây cơ mà mỗi nút có nhiều nhất nhị nút con: nút trái cùng nút phải.

Ở lấy một ví dụ 1, cây nhị phân có giá trị là root = <1,null,2,3>

Cây được diễn tả như hình bên với 1 là nút gốc, null là nút trái, 2 là nút phải, sau 2 còn quý hiếm là 3 đề nghị 3 là nút trái của cây con có gốc là 2.

Cây nhị phân được biểu diễn là một đối tượng của lớp đối tượng người dùng TreeNode với code Python như sau:

class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightĐể tạo nên cây với giá trị <1, null, 2, 3> thì leetcode đã giúp mình làm thao tác làm việc tạo cây này rồi, code của chính nó sẽ tương tự như vậy này.

root = TreeNode(1)root.right = TreeNode(2)root.right.left = TreeNode(3)Khi mình tiến hành print(root) là mình nhận được đối tượng người dùng ấy:

Inorder traversal

Inorder traversal là một cách thông qua cây nhị phân theo trang bị tự Left – Root – Right.

Ở đây chữ in diễn đạt nút gốc sẽ được duyệt sinh sống giữa, tức thiết bị tự là duyệt y nút trái, nút gốc rồi mang đến nút phải

Thuận toán Inorder Traversal rõ ràng là:

– chú ý cây bên trái (theo inorder traversal)

– trông nom nút gốc

– để ý cây bên nên (theo inorder traversal)

Hướng tiếp cận 1: Đệ quy

Tìm các bước được tái diễn và thành lập hàm đệ quy

Công bài toán được lặp lại

Để săn sóc cây trên với sản phẩm tự Left – Root – Right thì mình sẽ thực hiện như hình bên dưới và quăng quật qua các giá trị null mình thừa nhận được hiệu quả là <1, 3, 2>

Nếu nhằm ý bạn cũng có thể thấy tại địa chỉ số 2, chính là duyệt Left – Root – Right đến cây nhỏ từ địa chỉ này, và đó chính là quá trình được lặp lại.

Hàm đệ quy cho công việc được lặp lại

Công việc được tái diễn là: duyệt mặt trái, chăm chút gốc, duyệt mặt phải.

Tạo một hàm có tên là recursive_inorder_traversal với công việc trên và tiến hành gọi đệ quy cho bên trái, bên đề xuất như sau:

def recursive_inorder_traversal(root): """Recursive inorder traversal""" if root: # duyệt phía bên trái recursive_inorder_traversal(root.left) # chuẩn y gốc print(root.val) # coi xét bên cần recursive_inorder_traversal(root.right)Khi đó công dụng có được là:

Ví dụ về phong thái tạo cây và hàm đệ quy để mắt cây theo inorder traversal ngơi nghỉ đây, giả dụ thích chúng ta cũng có thể fork về repl.it xem thử.

À, dòng cây rất đẹp hông ^^, cái cây này mình lặt nó nghỉ ngơi trên ASCII Art ấy.

Code

Sau khi đã hiểu cách thức duyệt cây theo máy tự inorder traversal rồi, mình rất có thể sử dụng một danh sách tên là results nhằm lưu lại công dụng trên, và đấy là đáp án submit leetcode với phía này:

class Solution: def inorderTraversal(self, root): results = <> self.recursive_inorder_traversal(root, results) return results def recursive_inorder_traversal(self, root, results=None): """Recursive inorder traversal""" if root: # duyệt bên trái self.recursive_inorder_traversal(root.left, results) # chăm chú gốc results.append(root.val) # cẩn thận bên nên self.recursive_inorder_traversal(root.right, results)

Độ phức tạp

Từ bài này mình đã thử đi phân tích độ tinh vi của những hướng tiếp cận để dễ dãi hơn vào việc đánh giá phương án làm sao là về tối ưu hơn. Tất cả hai chỉ số hay sử dụng khi phân tích độ phức hợp của một thuật toán là: Time complexity cùng Space complexity.

Time complexity thể bây chừ gian, còn Space complexity diễn đạt cho việc sử dụng bộ nhớ.

(Cái này mình cũng còn tảo lần lắm buộc phải mình bao gồm đi xem thêm xung xung quanh nếu gồm gì sai sót mong cả nhà em chỉ bày nha.)

Time Complexity

Phương án này mình dùng đệ quy cẩn thận qua cây bên trái và bên phải, nên gồm T(n) = 2 * T(n/2) + 1

Do đó, time complexity là O(n)

Space Complexity

Phương án này mình cần sử dụng một biến hóa results lưu giữ kết quả:

– nếu cây nhị phân này mỗi gốc chỉ tất cả một nút thôi thì space đang là O(log n)

– ví như cây nhị phân này mỗi gốc gồm đủ nhì nút, thì space vẫn là O(n)

Do đó, space complexity là O(n)

Hướng tiếp cận 2: cần sử dụng ngăn xếp(stack)

Ngăn xếp là gì?

Ngăn xếp(stack) hoàn toàn có thể hiểu dễ dàng và đơn giản là một chiếc hộp giấy, nơi chúng ta có thể bỏ vào (push) các tờ giấy theo máy tự từ bên dưới lên trên, và khi ý muốn lấy ra(pop) thì mình đang lấy theo từ bên trên xuống dưới.

Nó bao gồm thứ từ bỏ là “vào sau – ra trước” hay “last in – first out” tuyệt LIFO.

Bạn bao gồm thể tìm hiểu thêm về phòng xếp làm việc Wikipedia tiếng Việt hoặc xem đoạn phim dưới trên đây nha.

https://youtu.be/CgFVgp_VCN8

Vì sao lựa chọn ngăn xếp?

Bạn có vướng mắc vì sao việc này rất có thể giải với ngăn xếp không nhỉ?

Đơn giản là chống xếp rất có thể giúp mình chứa các nút theo vật dụng tự với mình hoàn toàn có thể lấy ra với sản phẩm tự từ trên xuống dưới, thứ tự này tựa như như khi mình mang từ lá đến gốc

Còn đk để lấy 1 phần tử ra khỏi ngăn xếp là gì?

Nếu đã mất nút để duyệt(null) thì mình đã lấy nút từ phòng xếp ra, thêm cực hiếm của nút đó vào tác dụng rồi, chuyển nút kia thành nút tiếp theo cần để mắt rồi tiếp tục duyệt qua nút bên đề xuất của nút đó(vì phía trái đã chăm chú rồi).

*Vậy còn lúc nào thì lịch trình kết thúc? *

Chương trình sẽ ngừng khi chống xếp không thể nút nào nhằm lấy, với nút ở vị trí hiện tại là null.

Giải việc với phòng xếp

Mình sẽ sử dụng một đổi mới curr nhằm lưu nút lúc này đang duyệt, một đổi thay stack(list) nhằm lưu các nút cùng một đổi mới results(list) để lưu kết quả.

Ban đầu:

– curr có mức giá trị là root, tức mình ban đầu duyệt từ bỏ nút gốc

– stack cùng results có mức giá trị là <>

Cùng xem qua sơ đồ gia dụng mình vẽ cho bài toán này nhé(bạn có thể xem dạng slide show sống blog của chính bản thân mình nha).

*
*
*
*
*
*
*

Như vậy, mình hoàn toàn có thể thấy là thuở đầu biến curr có mức giá trị là root, tiến hành bỏ nút curr này vào stack, tiếp nối nó biến hóa thành curr.left và cứ thường xuyên bỏ vào stack cho tới khi curr.left là null, tức là đã mang lại nút lá sau cùng của cây sinh sống phía bên trái, thì nó sẽ ban đầu tiến hành rước từ chống xếp ra, đặt hiệu quả nút trái cuối cùng vào kế tiếp lại qua phía bên phải.

Tức là mình luôn luôn thực hiện nay theo trang bị tự Left – Root – Right theo đề bài bác yêu cầu.

Code

class Solution: def inorderTraversal(self, root): results = <> stack = <> curr = root while (curr or len(stack) != 0): while curr: stack.append(curr) curr = curr.left curr = stack.pop() results.append(curr.val) curr = curr.right return results

Độ phức tạp

Time Complexity: O(n)

Space Complexity: O(n)

Bài tập hôm nay đến đó là hết rồi, ai có cách giải làm sao xịn hơn thế thì nhớ phản hồi bày mình với nhé.

Xem thêm: Câu Nói Hay Tiểu Thuyết Ngôn Tình Trung Quốc, Những Trích Dẫn Ngôn Tình Hay Nhất

À, mình có tạo một danh sách những bài easy trên Leetcode nhưng mà mình thực hành ở đây, chúng ta cũng có thể Clone về tài khoản leetcode của doanh nghiệp để thực hành nhé.