Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

提示	解題應用
Tree	樹的遍歷方式
DepthFirstSearch	後序遍歷

Default:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxDepth(root *TreeNode) int {

}

解答思路:

(此題思路有修正，建議看完直接拉到最底下參考修正的部分)

決定一棵樹的深度，用深度優先遍歷是最好不過了，而就一節點來說其子節點有分左子節點與右子節點，要知道該節點的最大深度就必需要先比較左右兩子節點的深度，換句話說就是要等到左右節點都深度遍歷完了才有辦法做判斷，所以我們就要用後序遍歷來實作深度優先遍歷，當然用遞回的方式來做便再簡單不過了。

程式碼解說:

接下來就是用遞回的方式做處理，在一開始因為進來的節點有可能是nil該層的深度就不算數，所以需要回傳的是最大深度再-1，而如果節點存在當然就是繼續去做遞回，而因為要等左右節點的最大深度回來才能做比較，此為後序遍歷的方式判斷式都要在後頭

if node == nil {
	return maxRow - 1
}
var maxRowL int
var maxRowR int
maxRowL = postOrderTravel(node.Left, maxRow+1)
maxRowR = postOrderTravel(node.Right, maxRow+1)
if maxRowL >= maxRow && maxRowL >= maxRowR {
	return maxRowL
} else if maxRowR >= maxRow && maxRowR >= maxRowL {
	return maxRowR
}
return maxRow

完整程式碼:

func postOrderTravel(node *TreeNode, maxRow int) int {
	if node == nil {
		return maxRow - 1
	}
	var maxRowL int
	var maxRowR int
	maxRowL = postOrderTravel(node.Left, maxRow+1)
	maxRowR = postOrderTravel(node.Right, maxRow+1)
	if maxRowL >= maxRow && maxRowL >= maxRowR {
		return maxRowL
	} else if maxRowR >= maxRow && maxRowR >= maxRowL {
		return maxRowR
	}
	return maxRow
}
func maxDepth(root *TreeNode) int {
	return postOrderTravel(root, 1)
}

總結:

決定一棵樹的深度就用深度優先遍歷的方式，而因為需先比較左、右兩節點的深度才有辦法往上回傳最大深度，因此就要用後序遍序來實作深度優先遍歷。

修正:

主要是不需要用極大值、極小值的方式判斷路徑，直接從節點判斷左右子節點是否存在，再考慮需不需要遍歷該子節點，如此一來就可以省去非常多的麻煩，大多數關於樹的遍歷都可以用此方式處理。

func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	return preOrderTravel(root, 0)
}
func preOrderTravel(node *TreeNode, maxRow int) int {
	if node.Left == nil && node.Right == nil {
		return maxRow + 1
	} else if node.Left == nil {
		return preOrderTravel(node.Right, maxRow+1)
	} else if node.Right == nil {
		return preOrderTravel(node.Left, maxRow+1)
	}
	maxRowL := preOrderTravel(node.Left, maxRow+1)
	maxRowR := preOrderTravel(node.Right, maxRow+1)
	if maxRowL > maxRowR {
		return maxRowL
	}
	return maxRowR
}