二分木の外側のフレームを印刷する方法。
葉が 1 つしかないすべてのノードを出力します
100
/ \
50 150
/ \ /
24 57 130
/ \ \ \
12 30 60 132
例: 出力は 100、50、24、12、30、57、60、130、132、150 のようになります。
左ノード、葉ノード、右ノードを出力する 3 つの異なる関数を作成すると、簡単に解決できますが、O(n+2logn) 時間かかります。
O(n) アプローチも探していますが、条件は、各ノードを 1 回だけ訪問する必要があることです。この余分な O(2logn) 部分は必要ありません。
これは O(n) で実行できます。つまり、ツリーの各ノードに 1 回だけアクセスします。ロジックは次のとおりです。左右の 2 つの変数を保持 し、ゼロに初期化します。左側への再帰呼び出しがあるたびに、左に1 をインクリメントします。ライド側への再帰呼び出しがあるたびに、右に 1 をインクリメントします。
ルートから開始して、順番にトラバーサルを実行し、rightがゼロかどうかを確認します。これは、right を再帰的に呼び出したことがないことを意味します。yes がノードを出力する場合、これは tree のすべての左端のノードを出力していることを意味します。rightが 0 以外の場合、それらは境界とは見なされないため、リーフ ノードを探して出力します。
左サブツリーの呼び出しが完了した後の順序通りのトラバーサルでは、ルートまでバブルアップし、次に右サブツリーの再帰呼び出しを行います。最初にリーフノードをチェックして出力し、次にleftがゼロかどうかをチェックします。これは、 left を再帰的に呼び出したことを意味するため、境界とは見なされません。leftが 0 の出力ノードの場合、これは tree の右端のノードをすべて出力していることを意味します。
コードスニペットは
void btree::cirn(struct node * root,int left,int right)
{
if(root == NULL)
return;
if(root)
{
if(right==0)
{
cout<<root->key_value<<endl;
}
cirn(root->left,left+1,right);
if(root->left==NULL && root->right==NULL && right>0)
{
cout<<root->key_value<<endl;
}
cirn(root->right,left,right+1);
if(left==0)
{
if(right!=0)
{
cout<<root->key_value<<endl;
}
}
}
}
アルゴリズム:
- 左境界を印刷する
- 葉を印刷する
- 右側の境界を印刷する
void getBoundaryTraversal(TreeNode t) {
System.out.println(t.t);
traverseLeftBoundary(t.left);
traverseLeafs(t);
//traverseLeafs(t.right);
traverseRightBoundary(t.right);
}
private void traverseLeafs(TreeNode t) {
if (t == null) {
return;
}
if (t.left == null && t.right == null) {
System.out.println(t.t);
return;
}
traverseLeafs(t.left);
traverseLeafs(t.right);
}
private void traverseLeftBoundary(TreeNode t) {
if (t != null) {
if (t.left != null) {
System.out.println(t.t);
traverseLeftBoundary(t.left);
} else if (t.right != null) {
System.out.println(t.t);
traverseLeftBoundary(t.right);
}
}
}
private void traverseRightBoundary(TreeNode t) {
if (t != null) {
if (t.right != null) {
traverseRightBoundary(t.right);
System.out.println(t.t);
} else if (t.left != null) {
traverseLeafs(t.left);
System.out.println(t.t);
}
}
}
TreeNode意味：
class TreeNode<T> {
private T t;
private TreeNode<T> left;
private TreeNode<T> right;
private TreeNode(T t) {
this.t = t;
}
}
簡単な解決策は次のとおりです。
def printEdgeNodes(root, pType, cType):
if root is None:
return
if pType == "root" or (pType == "left" and cType == "left") or (pType == "right" and cType == "right"):
print root.val
if root.left is None and root.right is None:
print root.val
if pType != cType and pType != "root":
cType = "invalid"
printEdgeNodes(root.left, cType, "left")
def printEdgeNodes(root):
return printEdgeNodes(root, "root", "root")
在宅ワークの問題のようですが、練習が必要です。私は10年間、再帰で何もしていません。
void SimpleBST::print_frame()
{
if (root != NULL)
{
cout << root->data;
print_frame_helper(root->left, true, false);
print_frame_helper(root->right, false, true);
cout << endl;
}
}
void SimpleBST::print_frame_helper(Node * node, bool left_edge, bool right_edge)
{
if (node != NULL)
{
if (left_edge)
cout << ", " << node->data;
print_frame_helper(node->left, left_edge && true, false);
if ((!left_edge) && (!right_edge))
if ((node->left == NULL) || (node->right == NULL))
cout << node->data << ", ";
print_frame_helper(node->right, false, right_edge && true);
if (right_edge)
cout << ", " << node->data;
}
}
解決策は、ツリーを前の順序でトラバースすることで実行できます-O(n)。
以下のサンプルコードを見つけてください。ソースといくつかの説明。
Java のサンプル コード:
public class Main {
/**
* Prints boundary nodes of a binary tree
* @param root - the root node
*/
public static void printOutsidesOfBinaryTree(Node root) {
Stack<Node> rightSide = new Stack<>();
Stack<Node> stack = new Stack<>();
boolean printingLeafs = false;
Node node = root;
while (node != null) {
// add all the non-leaf right nodes left
// to a separate stack
if (stack.isEmpty() && printingLeafs &&
(node.left != null || node.right != null)) {
rightSide.push(node);
}
if (node.left == null && node.right == null) {
// leaf node, print it out
printingLeafs = true;
IO.write(node.data);
node = stack.isEmpty() ? null : stack.pop();
} else {
if (!printingLeafs) {
IO.write(node.data);
}
if (node.left != null && node.right != null) {
stack.push(node.right);
}
node = node.left != null ? node.left : node.right;
}
}
// print out any non-leaf right nodes (if any left)
while (!rightSide.isEmpty()) {
IO.write(rightSide.pop().data);
}
}
}