5.输出结果

试编写算法求给定二叉树上从根节点到叶子节点的一条路径长度等于树的深度减一的路径即列出从根节点到该叶子节点的节点序列若这样的路径存在多条则输出路径终点在“最左”的一条。

2.算法思想

计算出树的高度然后再进行类前序遍历输出路径为最深的、最靠左的一条。

分为两部分。

1.求树的高度2.求路径

这个算法在14年某个题已经涉及到了。

通过遍历的方式得出每一个结点的左子树高度和右子树高度而该结点的高度就是左子树高度和右子树高度较大的那一个1

2.2.求路径

由于是求最靠左的一条、最深的一条路径那么用类先序遍历的方式进行探索最有优势。

根据先序遍历的特点我们第一次找到的路径即为最左边的。

同时引入了一个变量isFound这样在找到一条路径之后可以更快跳过后续的递归嵌套。

3.关键代码

通过递归遍历二叉树查找根到叶子节点的路径其深度等于指定高度并打印该路径。

**

param

通过计算二叉树的高度创建对应高度的数组并在树中查找深度为高度减一的路径。

*

param

通过递归遍历二叉树查找根到叶子节点的路径其深度等于指定高度并打印该路径。

**

param

通过计算二叉树的高度创建对应高度的数组并在树中查找深度为高度减一的路径。

*

param

{printBinaryTree(root-lchild);}printf(

);if

{printBinaryTree(root-rchild);}}printf());

}/***

调整节点之间的间距printTreeStructure(root-rchild,

space

root-data);printTreeStructure(root-lchild,

space

createNode(15);root-lchild-lchild

createNode(3);root-rchild-lchild

createNode(12);root-rchild-rchild

createNode(18);root-rchild-lchild-rchild

createNode(13);root-rchild-rchild-rchild

createNode(9);//

Representation):\n);printBinaryTree(root);//

Tree

Structure:\n);printTreeStructure(root,

0);int

\n);findSpecialPath(root);return

}5.输出结果