每天刷个算法题20160521:二叉树高度(递归与非递归)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了每天刷个算法题20160521:二叉树高度(递归与非递归),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2425字,纯文字阅读大概需要4分钟。
内容图文
![每天刷个算法题20160521:二叉树高度(递归与非递归)](/upload/InfoBanner/zyjiaocheng/1208/b8d2047a818b4ba49776c6c7d772f934.jpg)
版权所有。所有权利保留。
欢迎转载,转载时请注明出处:
http://blog.csdn.net/xiaofei_it/article/details/51502727
为了防止思维僵化,每天刷个算法题。已经刷了几天了,现在发点代码。
我已经建了一个开源项目,每天的题目都在里面:
https://github.com/Xiaofei-it/Algorithms
绝大部分算法都是我自己写的,没有参考网上通用代码。读者可能会觉得有的代码晦涩难懂,因为那是我自己的理解。
最近几天都是在写一些原来的东西,大多数是非递归。以后准备刷点DP、贪心之类的题。
下面是二叉树高度(递归与非递归):
/** * * Copyright 2016 Xiaofei * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. * */ package xiaofei.algorithm; import java.util.Stack; /** * Created by Xiaofei on 16/5/21. * * I am writing code in Starbucks alone. * * What a sad picture!!! * * I cannot remember when I drank coffee with somebody else last time. * */ public class BinaryTreeHeight { public static int calculateRecursively(BinaryTreeNode root) { if (root == null) { return 0; } else { return Math.max(calculateRecursively(root.left), calculateRecursively(root.right)) + 1; } } public static int calculateCorecursively(BinaryTreeNode root) { //当年ACM的时候总喜欢自己写queue或者stack,几乎不用C++的STL库。现在想用一下Java的Stack class Element { BinaryTreeNode node; int left; int right; Element(BinaryTreeNode node) { this.node = node; left = right = -1; } } Stack<Element> stack = new Stack<>(); stack.push(new Element(root)); int result = -1; while (!stack.empty()) { Element element = stack.peek(); if (element.node == null) { stack.pop(); if (stack.isEmpty()) { result = 0; } else { Element tmp = stack.peek(); if (tmp.left == -1) { tmp.left = 0; } else { tmp.right = 0; } } } else if (element.left == -1) { stack.push(new Element(element.node.left)); } else if (element.right == -1) { stack.push(new Element(element.node.right)); } else { Element tmp1 = stack.pop(); int height = Math.max(tmp1.left, tmp1.right) + 1; if (stack.isEmpty()) { result = height; } else { Element tmp2 = stack.peek(); if (tmp2.left == -1) { tmp2.left = height; } else { tmp2.right = height; } } } } return result; } }
原文:http://blog.csdn.net/xiaofei_it/article/details/51502727
内容总结
以上是互联网集市为您收集整理的每天刷个算法题20160521:二叉树高度(递归与非递归)全部内容,希望文章能够帮你解决每天刷个算法题20160521:二叉树高度(递归与非递归)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。