首页 > 代码库 > 找树节点在二叉树中的深度
找树节点在二叉树中的深度
/**pRoot接收要检索的树的根节点,pNode是要确认深度的结点 path存储从根结点到pNode的所有节点,包括了pNode和根节点*/void findPath(BinaryTreeNode *pRoot, BinaryTreeNode *pNode, vector<int> &path){ if (pRoot == NULL) return; path.push_back(pRoot->m_nValue); if (pRoot == pNode){ //找到了节点,立即返回 printf("A path is found:\n"); return; } vector<int>::size_type preSize = path.size(); //若在左子树找到pNode,不要释放当前节点,立即返回 findPath(pRoot->m_pLeft, pNode, path); //巧妙的利用path的size增加来判断是否找到节点 if (preSize < path.size()) return; //若在左子树找到pNode,不要释放当前节点,立即返回 findPath(pRoot->m_pRight, pNode, path); //若在左子树找到pNode,不要释放当前节点,立即返回 if (preSize < path.size()) return; path.pop_back(); }
这题最容易错的是子树找到节点这种情况没有单独讨论,导致path.pop_back()执行,释放当前压入容器节点,产生逻辑错误。
最后只要把path.size()-1打印出来就是节点的深度了
从中可以看出递归写法可以简单优雅地把回溯思路表现出来,掌握递归的写法是程序员能力的一种体现。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。