数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程语言
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时装设计
法律C++ 程序查找二叉树中最深的左叶
一颗二叉树至多有 2 个子节点，指定为左子节点和右子节点。这是一个 C++ 程序，用于查找二叉树中最深层的左叶。
算法
Begin. function deepestLLeafutil() find the deepest left leaf in a given binary tree: lvel is level of current node. maxlvel is pointer to the deepest left leaf node found so far isLeft Indicates that this node is left child of its parent resPtr is Pointer to the result If root is equal to Null then Return. Update result if this node is having a left leaf and its level is more than the max level of the current result. Recursively call function deepestLLeafutil() for left and right subtrees. End.
代码示例
#include <iostream>
using namespace std;
struct n {
int v;
n *l, *r;
};
void deepestLLeafutil(n *root, int lvel, int *maxvel, bool isLeft, n **resPtr) {
if (root == NULL)
return;
if (isLeft && !root->l && !root->r && lvel > *maxvel) {
*resPtr = root;
*maxvel = lvel;
return;
}
deepestLLeafutil(root->l, lvel + 1, maxvel, true, resPtr);
deepestLLeafutil(root->r, lvel + 1, maxvel, false, resPtr);
}
n* deepestLLeaf( n *root) {
int maxlevel = 0;
n *res = NULL;
deepestLLeafutil(root, 0, &maxlevel, false, &res);
return res;
}
n *newnode(int d) {
n *t = new n;
t->v = d;
t->l = t->r = NULL;
return t;
}
int main() {
n* root = newnode(9);
root->l = newnode(7);
root->r = newnode(10);
root->l->l = newnode(6);
root->r->l= newnode(8);
root->r->r = newnode(19);
root->r->l->r = newnode(4);
root->r->r->r = newnode(20);
n *res = deepestLLeaf(root);
if (res)
cout << "The deepest left leaf is " << res->v;
else
cout << "There is no left leaf in the given tree";
return 0;
}输出结果
The deepest left leaf is 6
更新时间：2019 年 7 月 30 日
浏览量：148
广告