首页 > 代码库 > 剑指offer-二叉树的深度
剑指offer-二叉树的深度
题目:
输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。
链接:
http://www.nowcoder.com/practice/435fb86331474282a3499955f0a41e8b?tpId=13&tqId=11191&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
代码:
心血来潮用栈实现了一下树的后序递归遍历
1 /* 2 struct TreeNode { 3 int val; 4 struct TreeNode *left; 5 struct TreeNode *right; 6 TreeNode(int x) : 7 val(x), left(NULL), right(NULL) { 8 } 9 };*/10 class Solution {11 public:12 int TreeDepth(TreeNode* pRoot)13 {14 if(pRoot == NULL){15 return 0;16 }17 stack<TreeNode*> st;18 stack<bool> fst;19 TreeNode *top = pRoot;20 bool ftop;21 int maxDepth = 0;22 while(top != NULL || !st.empty()){23 while(top != NULL){24 st.push(top);25 fst.push(true);26 top = top->left;27 }28 29 top = st.top();30 ftop = fst.top();31 32 st.pop();33 fst.pop();34 if(ftop){35 st.push(top);36 fst.push(false);37 38 if(top->right == NULL && st.size() > maxDepth){39 maxDepth = st.size();40 }41 top = top->right;42 }else{43 top = NULL;44 }45 46 }47 48 return maxDepth;49 }50 };
剑指offer-二叉树的深度
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。