如何打印二叉树的外框。
打印所有只有 1 个叶子的节点
100
/ \
50 150
/ \ /
24 57 130
/ \ \ \
12 30 60 132
例如：输出应该是 100, 50, 24, 12, 30, 57, 60, 130, 132, 150
如果我们编写三个不同的函数来打印左节点、叶节点和右节点，这很容易解决，但需要 O(n+2logn) 时间。
我也在寻找一种 O(n) 方法，但条件是每个节点应该只访问一次，不想要这个额外的 O(2logn) 部分。
这可以在 O(n) 中完成。也就是说，我们只访问树的每个节点一次。逻辑如下 保持 左右两个变量，初始化为零。当递归调用左侧递增1时递归调用乘侧递增1
从 root 开始，进行中序遍历并检查right是否为零，这意味着我们从未对 right 进行递归调用。如果是打印节点，这意味着我们正在打印树的所有最左边的节点。如果右边不为零，它们不被视为边界，所以寻找叶子节点并打印它们。
在左子树调用完成后的中序遍历中，您冒泡到根，然后我们对右子树进行递归调用。现在首先检查叶子节点并打印它们，然后检查left是否为零，这意味着我们对left进行了递归调用，因此它们不被视为边界。如果left是零打印节点，这意味着我们正在打印 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;
}
}
解决方案可以通过按前序遍历树来完成 - 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);
}
}
}
您可以递归地遍历每个节点并控制何时打印，这是 javascript 代码片段。
function findBtreeBoundaries(arr, n, leftCount, rightCount) {
n = n || 0;
leftCount = leftCount || 0;
rightCount = rightCount || 0;
var length = arr.length;
var leftChildN = 2*n + 1, rightChildN = 2*n + 2;
if (!arr[n]) {
return;
}
// this is the left side of the tree
if (rightCount === 0) {
console.log(arr[n]);
}
// select left child node
findBtreeBoundaries(arr, leftChildN, leftCount + 1, rightCount);
// this is the bottom side of the tree
if (leftCount !== 0 && rightCount !== 0) {
console.log(arr[n]);
}
// select right child node
findBtreeBoundaries(arr, rightChildN, leftCount, rightCount + 1);
// this is the right side of the tree
if (leftCount === 0 && rightCount !== 0) {
console.log(arr[n]);
}
}
findBtreeBoundaries([100, 50, 150, 24, 57, 130, null, 12, 30, null, 60, null, 132]);
Seems like a home work problem, but I need the practice. I haven't done anything with recursion in a decade.
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;
}
}
这是一个简单的解决方案：
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")