Given a binary tree, print boundary nodes of the binary tree Anti-Clockwise starting from the root. For example, boundary traversal of the following tree is “20 8 4 10 14 25 22″
We break the problem in 3 parts:
1. Print the left boundary in top-down manner.
2. Print all leaf nodes from left to right, which can again be sub-divided into two sub-parts:
…..2.1 Print all leaf nodes of left sub-tree from left to right.
…..2.2 Print all leaf nodes of right subtree from left to right.
3. Print the right boundary in bottom-up manner.
We need to take care of one thing that nodes are not printed again. e.g. The left most node is also the leaf node of the tree.
Based on the above cases, below is the implementation:
// A simple function to print leaf nodes of a binary tree void printLeaves(struct node* root) { if ( root ) { printLeaves(root->left); // Print it if it is a leaf node if ( !(root->left) && !(root->right) ) printf("%d ", root->data); printLeaves(root->right); } } // A function to print all left boundry nodes, except a leaf node. // Print the nodes in TOP DOWN manner void printBoundaryLeft(struct node* root) { if (root) { if (root->left) { // to ensure top down order, print the node // before calling itself for left subtree printf("%d ", root->data); printBoundaryLeft(root->left); } else if( root->right ) { printf("%d ", root->data); printBoundaryLeft(root->right); } // do nothing if it is a leaf node, this way we avoid // duplicates in output } } // A function to print all right boundry nodes, except a leaf node // Print the nodes in BOTTOM UP manner void printBoundaryRight(struct node* root) { if (root) { if ( root->right ) { // to ensure bottom up order, first call for right // subtree, then print this node printBoundaryRight(root->right); printf("%d ", root->data); } else if ( root->left ) { printBoundaryRight(root->left); printf("%d ", root->data); } // do nothing if it is a leaf node, this way we avoid // duplicates in output } } // A function to do boundary traversal of a given binary tree void printBoundary (struct node* root) { if (root) { printf("%d ",root->data); // Print the left boundary in top-down manner. printBoundaryLeft(root->left); // Print all leaf nodes printLeaves(root->left); printLeaves(root->right); // Print the right boundary in bottom-up manner printBoundaryRight(root->right); } }
References:
http://www.geeksforgeeks.org/boundary-traversal-of-binary-tree/
http://articles.leetcode.com/2010/10/print-edge-nodes-boundary-of-binary.html
相关推荐
基于奇异摄动理论的柔性机械臂的复合PDE边界控制,刘志杰,刘金琨,本文提出了一种基于偏微分方程建模的柔性机械臂的复合边界控制策略。 首先运用奇异摄动理论将柔性机械臂PDE模型分解成两个简单的��
On the Solution of Lambert's Orbital Boundary-Value Problem During the past 30 years there has been a resurgence of interest in the classical orbital boundary value problem of Lambert, largely ...
用于图像识别,对于图像检测这一块非常有用
Adaptive boundary control of a flexible manipulator with input saturation
In addition to testing, Boundary-Scan offers the flexibility for a device to have its own set of user-defined instructions. The added common vendor-specific instructions, such as configure and ...
一种基于磷的非平衡晶界偏聚的晶界脆性预报方法,李庆芬,李莉,本文提出了一种利用磷的非平衡晶界偏聚机制对钢的晶界脆性进行预报的方法。
Uniform convergence analysis of an upwind finite difference approximations of an homogenous singularly perturbed boundary value problem using grid equidistribution,孙力楠,王安涛,We derive var...
非散度型二阶椭圆型方程大解的边界行为,高璐,张志军,本文主要研究非散度型二阶椭圆型方程大解的边界行为.应用摄动方法、Karamata 正规变化理论和比较原理, 在权函数和非线性项满足进一步
Freeman Chain Code Gives Freeman chain code 8-connected representation of a boundary
超复分析的Cauchy型积分的边界行为,杜金元,,本文综述了定义在一个光滑封闭曲面上取值在Clifford代数上或者定义在特征边界取值泛Clifford代数上的Cauchy型积分的边界行为方面的研究�
哈密顿系统拉格朗日边值问题及塞福特猜测,刘春根,,我们在这篇综述文章里介绍哈密顿系统拉格朗日边值问题和塞福特猜测的一些研究现状和近几年的一些新的进展。
Boundary
基于NURBS的曲边单元边界逼近研究,张永杰,张晓虎,传统曲边单元对于复杂单元边界的描述主要基于插值节点和形状函数,其精度依赖于节点数量和形状函数阶次;为了更加准确逼近复杂边
Find boundary edge of an image.
配电支持生成器(BDSG)边界上的样本生成_Boundary of Distribution Support Generator (BDSG) Sample Generation on the Boundary.pdf
this paper presents a novel method of buffer generation based on vector boundary tracing. The new method can avoid complex vector calculations, such as line and curve segment intersection, clipping ...
带非阻尼和扩散的非线性发展方程零扩散极限的边界层,彭红云,阮立志,文考虑某种带阻尼和扩散的非线性发展方程,主要研究了当扩散参数β趋于0时的边界层效应和收敛率,并给出了边界层厚度的阶数O(βr)(0<...
Boundary fitting of extracted objects using LIFS Boundary Fitting of Extracted Objects Using LIFS Takashi Ida, Yoko Sambonsugi, and Toshiaki Watanabe Research and Development Center, Toshiba ...
磷的晶界偏聚的临界时间及扩散系数的研究,刘二宝,李庆芬,本文对12Cr1MoV钢不同固溶处理工艺下磷及复合体在晶界偏聚过程中的扩散系数及临界时间进行了研究。
This condition has been essential for the success of the introduction of a Boundary-Scan Test (BST) at board level. Since Boundary-Scan testing involves the whole PCB life cycle, it is more than just...