我的代码：直接用了以前那个求二叉树某一个条路径的和为特定值的思想
源代码
struct TreeNode{ int val; struct TreeNode *left; struct TreeNode *right; };
#ifndef BINARY_TREE_DEEP_H#define BINARY_TREE_DEEP_H#include "reconstructBinaryTree.h"#include<stack>#include<set>void treeDeepCore(TreeNode *node ,std::stack<TreeNode*> &v_stack,std::set<int> &v_set); int getBinaryTreeDeep(TreeNode **root){ if(root==NULL||*root==NULL){ return 0; } std::stack<TreeNode*> g_stack; std::set<int> g_set; treeDeepCore(*root,g_stack,g_set); std::cout<<*(g_set.begin())<<std::endl; return *(g_set.rbegin()); }void treeDeepCore(TreeNode *node ,std::stack<TreeNode*> &v_stack,std::set<int> &v_set){ if(node==NULL){ return; } v_stack.push(node); if(node->left==NULL&&node->right==NULL){ v_set.insert(v_stack.size()); } treeDeepCore(node->left,v_stack,v_set); treeDeepCore(node->right,v_stack,v_set); if(!v_stack.empty()){ v_stack.pop(); }}#endif
测试代码
#include"binaryTreeDeep.h"int main(){ int pre[8]={1,2,4,7,3,5,6,8}; int mid[8]={4,7,2,1,5,3,8,6}; struct TreeNode *root=reconstructBinaryTree(pre,mid,8); //重建二叉树 std::cout<<getBinaryTreeDeep(&root); }
如上图中，求棵树的深度我们其实可以这样，无非就是求最大路径的长度嘛，用递归的思想就可以解决这个问题了。
你看最大深度无非就是以下几种情况：
左子树为空，右子树不为空：深度为左子树的深度加1嘛
左子树不为空，右子树为空：深度为右子树的深度加1嘛
左右子树都不为空: 深度为两者中最大的深度为1嘛
int binaryTreeDeepCore(TreeNode *node){ if(node==NULL){ return 0; } int leftDeep=binaryTreeDeepCore(node->left); int rightDeep=binaryTreeDeepCore(node->right); return (leftDeep>rightDeep)? (leftDeep+1):(rightDeep+1); }
在这个基础上判断一棵树是不是平衡二叉树，于是知，也就是看一棵树是否存在两个左右节点深度差大于1嘛。
源代码
#ifndef IS_BALANCETREE_H#define IS_BALANCETREE_H#include"reconstructBinaryTree.h"int binaryTreeDeepCore(TreeNode *node); bool isBalanceBT(TreeNode *root){ if(root==NULL){ return true; } int leftDeep=binaryTreeDeepCore(root->left); int rightDeep=binaryTreeDeepCore(root->right); int diffDeep=leftDeep-rightDeep; if(diffDeep>1||diffDeep<-1) return false; return binaryTreeDeepCore(root->left)&&binaryTreeDeepCore(root->right); }int binaryTreeDeepCore(TreeNode *node){ if(node==NULL){ return 0; } int leftDeep=binaryTreeDeepCore(node->left); int rightDeep=binaryTreeDeepCore(node->right); return (leftDeep>rightDeep)? (leftDeep+1):(rightDeep+1); }#endif
来自为知笔记(Wiz)
转载于:https://www.cnblogs.com/yml435/p/4655471.html
相关资源：二叉排序树与平衡二叉树的实现
