1. 二叉树： （1） 最大深度： 递归， 最大深度等于左子树最大深度和右子树最大深度之间的最大值 + 1。 （2） 最小深度： 递归，当左右子树均不为空时，最小深度等于左子树和右子树的最小深度之间的最小值 +1， 当有一边子树为空时，最小深度等于左子树最小深度和右子树最小深度之间的最大值+1. （3）Symmetric Tree: 判断树是否是镜像树： 递归的判断两棵树是否镜像，条件： 根节点的值相同...
我们从二叉树的遍历谈起。 众所周知，在对二叉树的遍历过程中，根据遍历每一个结点的左子树、结点本身、右子树的顺序不同可将对二叉树的遍历方法分为前序遍历、中序遍历、后序遍历。我们摒弃数据结构教科书上复杂的遍历方式，而是使用我们在上一章所重点讨论过的递归程序来简单的实现它。 假设二叉树结点由以下结构体表示： struct Node {Node *lchild;//指向其左儿子结点的指针，当其不存在左儿子时为NULL Node *rchild;//指向其...
一 二叉查找树 二叉查找树又叫二叉排序树，是为了解决查找的效率问题。正常情况下查找一个元素，需要O（n）的代价，但是如果查找元素有顺序，有序数组：可以用二分查找降低到 lgn 代价，但是有序链表的代价还是O（n） 因为，链表不支持随机访问，定位不到中间元素，从而不可以一次就排除掉一半元素。此时二叉查找树的出现，完美解决了这个问题，左边的全比根小，右边的全比根大。所以理想状态下也是一次淘汰一半元素（当然不理想，...
目录 1 递归实现 1.1 思路 1.2 代码 2 非递归实现 2.1 思路 2.2 代码 1 递归实现 1.1 思路 底层是由栈实现，若根节点非空，先打印根节点，之后递归到根节点的左孩子节点...当遇到null节点时，返回；此时第6行代码执行完毕，进入第7行代码，注意此时递归后的节点，访问到当前节点的右孩子节点又进入递归~刚开始理解递归有些难，但这要自己慢慢琢磨、摸索代码~ 1.2 代码void binaryTreePrevOrder1(TreeNode root){if (root == null){...
二叉树（Binary Tree）是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。二叉树的特点： 1、任何一个结点的子结点数量不超过2 2、左、右子树有序不可颠倒 特殊的二叉树： 1、斜树所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。 2、满二叉树在一棵二叉树中，如果所有分支结点...
import java.util.Scanner;public class BinaryTree {private int info; private BinaryTree left; private BinaryTree right; private int height = 1;public BinaryTree() {left = null;right = null; }public BinaryTree(int theInfo) {Scanner sc = new Scanner(System.in);int intNum;String s;info = theInfo;System.out.print("Does the node " + info + " have a left child (y or n)? ");s = sc.next();if (s.equals("y")...
# 求二叉树每层的最大值 def greatest_nodes(root):if not root:return Nonenext_layer = [root]res = []while next_layer:temp_next_layer = []layer_value = []for node in next_layer:if not node:continuelayer_value.append(node.val)if node.left:temp_next_layer.append(node.left)if node.right:temp_next_layer.append(node.right)next_layer = temp_next_layerres.append(max(layer_value))return res
welcome to my blog 剑指offer面试题7(java版):重建二叉树 题目描述 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。 思路画图思考不容易越界 体会递归思想 本题在递归中传递的参数中, 不变的是两个表示前序遍历和中序遍历的数组, 变化的是代表子树起始索引和终止...
/*** 实现二叉树的创建、前序遍历、中序遍历和后序遍历**/package DataStructure;/*** Copyright 2014 by Ruiqin Sun* All right reserved* created on 2014-9-9 下午2:34:15**/public class BinTreeInt {private Node root;/*** 创建内部节点类**/private class Node{// 左节点private Node leftChild;// 右节点private Node rightChild;// 节点对应的值private int data;public Node(int data){this.leftChild = null;this.r...
class Node:def __init__(self,item):self.item = itemself.lchild = Noneself.rchild = Noneclass BinaryTree:def __init__(self, node=None):self.root = nodedef add(self, item):if self.root is None:self.root = Node(item)else:queue = []queue.append(self.root)while len(queue) > 0:node = queue.pop(0)if not node.lchild:node.lchild = Node(item)returnelse:queue.append(node.lchild)if not node.rchild:node.rchild...
解题思路： 使用递归的方法，递归比较左右子树深度，返回较大的值 + 1。/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/ class Solution { public:int maxDepth(TreeNode* root) {if(!root) return 0;else return max(maxDepth(root->left), maxDepth(root->right)) + 1;} };
我编写了一个删除树的所有元素的代码.需要以下建议： >在reverseTreeStack方法中,我可以不使用堆栈方法参数进行设计吗？>我可以用更好的设计在1种方法中设计整个代码吗？ 更新：将reverseTreeStack的返回类型更改为void.Removed堆栈的附加变量.public class DeleteTree {public static void deleteTree(BinaryTreeNode root){ Stack stack = new Stack();reverseTreeStack(stack, root);while (!stack.isEmpty()){BinaryTree...
1 树概述树：在层次化的数据元素之间有祖先-后代、上级-下属、整体-部分以及其他类似的关系。 根和子树：树t为非空有限集合，其中一个元素为根，其余组成t的子树。 级：树根为1级，其孩子是2级，孩子的孩子为3级，以此类推。 高度（深度）：树中级的个数。 元素的度：其孩子的个数。 树的度：其元素的度的最大值。2 二叉树特性及常用操作 2.1 二叉树特性 与普通树根本区别： （1）每个元素恰好有两棵子树 （2）每个元素的子树是有序...
思路：在数据结构中，有一个条件反射，谈及二叉树，就递归。所以在实现重建二叉树时，也应该用到递归的思想。 在前序遍历中，根节点处于第一个；在中序遍历中，根节点的左边为左子树节点，根节点右边为右子树节点。 根据性质构造根节点。 1、取出前序遍历的第一个节点作为根节点 2、在中序遍历中按照根节点分割左子树和右子树 3、递归 代码： class Solution: ????# 返回构造的TreeNode根节点 ????def reConstructBinaryTree(self,...
JAVA实现，供大家吐槽； import java.util.concurrent.atomic.AtomicInteger;public class BinTree {public static void main(String[] args) {TreeNode binTree = new BinTree.TreeNode("H");binTree.push("O").push("L").push("M").push("A").push("C").push("Y");binTree = binTree.push("B");TreeNode base = TreeHandler.findBase(binTree);System.out.println("---------------------------------------");TreeHandler.prin...