Python是一種高級編程語言,它有著強大的功能和豐富的庫,使得很容易在Python中實現(xiàn)各種算法。對于求樹的深度,Python提供了很多解決方法,其中比較常用的是遞歸方法。
def maxDepth(root): if not root: return 0 else: left_depth = maxDepth(root.left) right_depth = maxDepth(root.right) return max(left_depth, right_depth) + 1
上面這段代碼是一個求樹深度的遞歸方法。對于一顆二叉樹來說,它的深度是左子樹深度和右子樹深度的最大值加上1。
其中root表示當前子樹的根節(jié)點,如果root是空節(jié)點,返回0;否則遞歸求左子樹的深度和右子樹的深度,并返回它們的最大值再加上1,即為當前子樹的深度。
除了遞歸方法,Python還可以使用BFS(廣度優(yōu)先搜索)來求樹深度。代碼如下:
def maxDepth(root): if not root: return 0 queue = [root] depth = 0 while queue: size = len(queue) for i in range(size): cur = queue.pop(0) if cur.left: queue.append(cur.left) if cur.right: queue.append(cur.right) depth += 1 return depth
這段代碼使用了隊列來實現(xiàn)BFS。對于每一層的節(jié)點,先將它們從隊列中取出,再將它們的子節(jié)點加入隊列中。只有當隊列為空時,深度才會加1,并返回深度。
總結(jié):Python中求樹的深度有多種方法,其中遞歸和BFS是比較常用的方法。無論是哪種方法,都需要先理清楚樹的結(jié)構(gòu),以及樹的深度的定義。只有了解了這些,才能更好地解決問題。
下一篇vue分段編輯效果