問題
二分木の各要素が持つ値のうち, 最大のものを求めよ.
解法
２分探索木ではないので, 全要素をチェックして最大のものを返却する必要があります.１つ目の解法では幅優先探索で全nodeを走査し, その時点での最大値を見つけるたびにそれを変数に格納しておきます.
そうすると, 走査が終えた時点でその変数には最大値が格納されていることになります. Python版のコードは以下のようになります.
algorithms_trees_find_maximum_element_in_binary_tree_01.py
'''
The definition of tree node is like:
class Node():
def __init__(self, value):
self.value, self.left, self.right = value, None, None
def setValue(self, value):
self.value = value
def setLeft(self, left):
self.left = left
def setRight(self, right):
self.right = right
'''
def find_max(root):
if not root:
return None
queue = [root]
max_value = root.value
while queue:
new_queue = []
for node in queue:
if node.left:
max_value = max(max_value, node.left.value)
new_queue.append(node.left)
if node.right:
max_value = max(max_value, node.right.value)
new_queue.append(node.right)
queue = new_queue
return max_value
計算量は要素数をNとしてO(N), 空間量もO(N)となります(N-1個の子がすべてrootにぶら下がっていた場合, queueにはO(N)の要素数の格納が必要となるため). binary treeの幅優先探索にqueueを使うのは頻出です.
あるいは, 親要素を与えられた時に左の子要素達, 右の子要素達から最大値を求めるような関数を定義してやるとこの問題は再帰的に解くこともできます.
algorithms_trees_find_maximum_element_in_binary_tree_02.py
def find_max_value_from_parent_and_children(node):
if not node:
return None
if node.left and node.right:
return max(node.value, max(find_max_value_from_parent_and_children(node.left), \
find_max_value_from_parent_and_children(node.right)))
elif node.left:
return max(node.value, find_max_value_from_parent_and_children(node.left))
elif node.right:
return max(node.value, find_max_value_from_parent_and_children(node.right))
else:
node.value
def find_max(root):
return find_max_value_from_parent_and_children(root)
この場合も計算量, 空間量は同じくO(N)となります.
Java版のコードを記載しておきます。
1.BFS版
algorithms_trees_find_maximum_element_in_binary_tree_01.java
/* The definition of a node of tree is like:
public class Node {
public int value;
public Node left;
public Node right;
public Node(int value) {
this.value = value;
left = null;
right = null;
}
public setValue(int value) {
this.value = value;
}
public setLeft(Node left) {
this.left = left;
}
public setRight(Node right) {
this.right = right;
}
}
*/
public class Solution {
public static int findMax(Node root){
if (root == null) return Integer.MIN_VALUE;
int maxValue = root.value;
List<Node> lst = new ArrayList<Node>(root);
while (!lst.isEmpty()) {
List<Node> newLst = new ArrayList<Node>();
if (lst.left != null) {
newLst.add(lst.left);
if (lst.left > maxValue) maxValue = lst.left;
if (lst.right != null) {
newLst.add(lst.right);
if (lst.right > maxValue) maxValue = lst.right;
}
lst = newLst;
}
return maxValue;
}
}
2.再帰版
algorithms_trees_find_maximum_element_in_binary_tree_02.java
public class Solution {
public static int findMaxFromParentAndChildren(Node node) {
if (node == null) return Integer.MIN_VALUE;
if (node.left != null && node.right != null) {
return Math.max(node.value,
Math.max(Solution.findMaxFromParentAndChildren(left),
Solution.findMaxFromParentAndChildren(right)));
} else if (node.left != null) {
return Math.max(node.value,
Solution.findMaxFromParentAndChildren(left));
} else if (node.right != null) {
return Math.max(node.value,
Solution.findMaxFromParentAndChildren(right));
} else {
return node.value;
}
}
public static int findMax(Node root){
return Solution.findMaxFromParentAndChildren(root);
}
}