04081: 树的转换
http://cs101.openjudge.cn/practice/04081/
我们都知道用“左儿子右兄弟”的方法可以将一棵一般的树转换为二叉树，如：
0 0
/ | \ /
1 2 3 ===> 1
/ \ \
4 5 2
/ \
4 3
\
5现在请你将一些一般的树用这种方法转换为二叉树，并输出转换前和转换后树的高度。
输入
输入是一个由“u”和“d”组成的字符串，表示一棵树的深度优先搜索信息。比如，dudduduudu可以用来表示上文中的左树，因为搜索过程为：0 Down to 1 Up to 0 Down to 2 Down to 4 Up to 2 Down to 5 Up to 2 Up to 0 Down to 3 Up to 0。 你可以认为每棵树的结点数至少为2，并且不超过10000。
输出
按如下格式输出转换前和转换后树的高度： h1 => h2 其中，h1是转换前树的高度，h2是转换后树的高度。
样例输入
dudduduudu样例输出
2 => 4思路：感觉很久没有建树了，练习了建树。对于输入序列，‘ud’表示兄弟节点，单独‘d’表示子节点，‘u’表示回归到父节点。据此建立二叉树
python
# 赵思懿，生科
class BinaryTreeNode:
def __init__(self):
self.parent = None
self.left = None
self.right = None
def tree_height(root): # 计算二叉树高度
if not root:
return -1
else:
return max(tree_height(root.left), tree_height(root.right)) + 1
def original_tree_height(arr): # 原树高度
height, max_height = 0, 0
for action in arr:
if action == 'd':
height += 1
elif action == 'u':
height -= 1
max_height = max(max_height, height)
return max_height
def build_binary_tree(arr): # 根据输入序列建立二叉树
root = BinaryTreeNode()
current_node = root
for action in arr:
if action == 'd':
current_node.left = BinaryTreeNode()
current_node.left.parent = current_node
current_node = current_node.left
elif action == 'x':
current_node.right = BinaryTreeNode()
current_node.right.parent = current_node.parent
current_node = current_node.right
elif action == 'u':
current_node = current_node.parent
return root
input_sequence = input().replace('ud', 'x')
binary_tree_root = build_binary_tree(input_sequence)
print(original_tree_height(input_sequence), '=>', tree_height(binary_tree_root))python
# 23n2300011072(X)
class TreeNode:
def __init__(self):
self.children = []
self.first_child = None
self.next_sib = None
def build(seq):
root = TreeNode()
stack = [root]
depth = 0
for act in seq:
cur_node = stack[-1]
if act == 'd':
new_node = TreeNode()
if not cur_node.children:
cur_node.first_child = new_node
else:
cur_node.children[-1].next_sib = new_node
cur_node.children.append(new_node)
stack.append(new_node)
depth = max(depth, len(stack) - 1)
else:
stack.pop()
return root, depth
def cal_h_bin(node):
if not node:
return -1
return max(cal_h_bin(node.first_child), cal_h_bin(node.next_sib)) + 1
seq = input()
root, h_orig = build(seq)
h_bin = cal_h_bin(root)
print(f'{h_orig} => {h_bin}')一般的树因为是深搜，所以d和u的数量是匹配的，只需要找到down最多的次数就可以；转换成二叉树后的新 树，因为同一层除左孩外其余均是左孩的子节点，所以每次有d时把新高度+1，存储在栈中，每次在原来的基础上增加高度。
python
"""
calculates the height of a general tree and its corresponding binary tree using the
"left child right sibling" method. The input is a string composed of "u" and "d",
representing the depth-first search information of a tree.
uses a stack to keep track of the heights of the nodes in the binary tree.
When it encounters a "d", it increases the heights and updates the maximum heights if necessary.
When it encounters a "u", it decreases the old height and sets the new height to the top of the stack.
Finally, it returns the maximum heights of the tree and the binary tree in the required format.
"""
def tree_heights(s):
old_height = 0
max_old = 0
new_height = 0
max_new = 0
stack = []
for c in s:
if c == 'd':
old_height += 1
max_old = max(max_old, old_height)
new_height += 1
stack.append(new_height)
max_new = max(max_new, new_height)
else:
old_height -= 1
new_height = stack[-1]
stack.pop()
return f"{max_old} => {max_new}"
s = input().strip()
print(tree_heights(s))思路：根据dfs序列递归建树，但并不需要把树转换为实体二叉树，可以递归地求高度(Height)和转换后高度(NewH)。
python
# 卢卓然 生命科学学院
class Node:
def __init__(self):
self.child = []
def getHeight(self):
return 1 + max([nd.getHeight() for nd in self.child], default=-1)
def getNewH(self):
return 1 + max([nd.getNewH() + i for i, nd in enumerate(self.child)], default=-1)
def call():
res = Node()
while s and s.pop() == 'd':
res.child.append(call())
return res
s = list(input())[::-1]
root = call()
print(f"{root.getHeight()} => {root.getNewH()}")思路：我写的方法还是分别建起来两个树，其中左儿子右兄弟方法建树还挺麻烦的，但是后来一想，每一个节点都是左儿子右兄弟方法建树，那不就是递归吗。
python
# 蔡嘉华 物理学院
class TreeNode:
def __init__(self):
self.children = []
self.left = None
self.right = None
def height1(root):
if not root:
return -1
elif not root.children:
return 0
h = 0
for child in root.children:
h = max(h, height1(child))
return h + 1
def height2(root):
if not root:
return -1
elif not root.left and not root.right:
return 0
return 1 + max(height2(root.left), height2(root.right))
root = TreeNode()
nodes = [root]
steps = list(input())
for step in steps:
if step == 'd':
node = TreeNode()
nodes[-1].children.append(node)
nodes.append(node)
else:
nodes.pop()
def prase_tree(root: TreeNode):
if root.children:
root.left = prase_tree(root.children.pop(0))
cur = root.left
while root.children:
cur.right = prase_tree(root.children.pop(0))
cur = cur.right
return root
h1 = height1(root)
root0 = prase_tree(root)
h2 = height2(root0)
print(f'{h1} => {h2}')c++
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main()
{
string str;
cin >> str;
int oldheight = 0;
int maxold = 0;
int newheight = 0;
int maxnew = 0;
stack<int> s;
for (int i=0; i<str.size(); i++) {
if (str[i] == 'd') {
oldheight++;
if (oldheight > maxold)
maxold = oldheight;
newheight++;
s.push(newheight);
if (newheight > maxnew)
maxnew = newheight;
}
else {
oldheight--;
newheight = s.top();
s.pop();
}
}
cout << maxold << " => " << maxnew << endl;
}