判断满二叉树 public class Node{int value;Node left;Node right; } int deep(Node root){if(root==null){return 0;}int leftDepth = deep(root.left);int rightDepth = deep(root.right);return rightDepth>leftDepth?rightDepth+1:leftDepth+1; } bool isFullBinTree(Node root){if(root==null){return false;}if(root.left==null&&root.right==null){return true;}int leftDepth = deep(root.left);int rightDepth = deep(root...
首先我们了解一下树： 树状图是一种数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点： 每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树 那我们再树之前来看看数组的底层 数组如果不够需要扩容，比较麻烦需要创建...
题目： 路径总和 II：给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。 说明: 叶子节点是指没有子节点的节点。 示例:给定如下二叉树，以及目标和 sum = 22，5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1返回: [ [5,4,11,2], [5,8,4,5]] 思路： 老深度优先了。 程序：# Definition for a binary tree node. # c...
题目： 求根到叶子节点数字之和：给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。 例如，从根到叶子节点路径 1->2->3 代表数字 123。 计算从根到叶子节点生成的所有数字之和。 说明: 叶子节点是指没有子节点的节点。 思路： 深度优先。 程序：# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left...
条件：【1】需要将原来树的节点重新封装，封装后的结构中具有对原来树节点的一个flag描述；【2】利用STL中的栈容器实现对节点的入栈以及出栈操作； 拿下图为例： 注意：该段代码实现的是前序遍历，如果想要实现中序/后序遍历 只需将第48-49行代码与前俩行代码调换位置即可。该段代码没有对new过的节点进行delete。（暂时不知道怎么delete !-!）。 1 #include<iostream>2 #include<stack>3 using namespace std;4 5 const int...
105. 从前序与中序遍历序列构造二叉树题目来源：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal 题目根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如，给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]返回如下的二叉树：3/ 9 20/ 15 7解题思路思路：递归 在这里，先讲一下前序遍历和中序遍历的概念。前...
题目描述请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。 ? ? 链接：https://www.nowcoder.com/questionTerminal/ff05d44dfdb04e1d83bdbdab320efbcb?f=discussion来源：牛客网 //===================递归算法=============================// 1.只要pRoot.left和pRoot.right是否对称即可 2.左右节点的值相等且对称子树left.left， right.right ;left.rigth,ri...
class BiTNode:def __init__(self, data, left, right):self.data = dataself.left = leftself.right = right t = BiTNode(10, BiTNode(2,None,None), BiTNode(3,None,None)) def sum_tree(t:BiTNode):total=0if t != None:total += t.datatotal += sum_tree(t.left)total += sum_tree(t.right)return total sum_tree(t)15
题目： 路径总和：给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。 说明: 叶子节点是指没有子节点的节点。 示例: 给定如下二叉树，以及目标和 sum = 22，5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。 思路： 野路子...
题目： 二叉树的层次遍历 II：给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历） 思路： 正常层序遍历结果的逆输出。 程序：# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution:def levelOrderBottom(self, root: TreeNode) -> Li...
题目： 验证二叉搜索树：给定一个二叉树，判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征： 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 思路： 遇到树第一想到了递归，用递归来实现。 程序 ：# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self...
题目： 二叉树的锯齿形层次遍历：给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。 思路： 使用层序遍历的思路，但是没有用到栈。 程序：# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution:def zigzagLevelOrder(s...
一、Node节点的java实现 首先在可以看到打上Node这个字符串，就可以看到只能的IDEA系统提供的好多提示：点进去看，却不是可以直接构成二叉树的Node，不是我们需要的东西。这里举个例子来看 org.w3c.dom 这里面的Node是一个接口，是解析XML时的文档树。在官方文档里面看出：该 Node 接口是整个文档对象模型的主要数据类型。它表示该文档树中的单个节点。当实现 Node 接口的所有对象公开处理子节点的方法时，不是实现 Node 接口的所有...
给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么这个节点的值不大于它的子节点的值。 给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。来源：力扣（LeetCode）/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int...
二叉搜索树的代码实现，有插入、查找、删除等基本功能。 需要注意的是，当类中有私有类pClass且在类外声明的成员函数的返回值是pClass类型的时候，需要在pClass前加typename。比如说template <typename Comparable> typename binarysearchtree<Comparable>::BinaryNode* binarysearchtree<Comparable>::findMax(BinaryNode* t)const {if (t == NULL) return NULL;if (t->right == NULL) return t;return findMin(t->right); }这里的...