1 /**2 * C++ 语言: 二叉查找树3 *4 * @author skywang5 * @date 2013/11/076 */7 8 #ifndef _BINARY_SEARCH_TREE_HPP_9 #define _BINARY_SEARCH_TREE_HPP_10 11 #include <iomanip>12 #include <iostream>13 using namespace std;14 15 template <class T>16 class BSTNode{17 public:18 T key; // 关键字(键值)19 BSTNode *left; // 左孩子20 BSTNode *right; // 右孩子21...
一、 二叉树的构建及其遍历.编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。 输入 abc##de#g##f### 输出 c b e g d f a通过遍历字符串中的字符来创建节点，遇到#就向后移动，直到返回null结束。import java.util.*; class Node...
剑指 Offer 32 - II. 从上到下打印二叉树 II/*** 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:vector<vector<int>> levelOrder(TreeNode* root) { // 层次遍历，默写题vector<vector<int>> result;vector<int> V;queue<TreeNode*> Q;TreeNode* p;if(root) Q.pus...
剑指 Offer 33. 二叉搜索树的后序遍历序列class Solution { public:bool buildTree(vector<int> &postorder, vector<int> &inorder, int postL, int postR, int inL, int inR) {if(postR == postL && inR == inL) return true;if(postR - postL != inR - inL) return false;int cnt = 0;while(inL + cnt < inR && inorder[inL + cnt] != postorder[postR-1]) cnt++;if(inL + cnt >= inR) return false;bool left_flag = buildTree(...
先序遍历：根左右 中序遍历：左根右 后序遍历：左右根 建树 public class BinaryTree {TreeNode root;public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) {this.val = val;}TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}}public BinaryTree(Integer[] array) {//建树root = new TreeNode(array[1]);TreeNode[] treeNodes =...
数据结构-二叉树编程 求二叉树叶子数量如果节点的左子树与右子树相同且为NULL int num=0;void GetLeavesNum(BN* a){ if (a == NULL) return; if (a->lchild == NULL && a->rchild == NULL) { num++; } GetLeavesNum(a->lchild); GetLeavesNum(a->rchild);}? 求二叉树的高度左子树和右子树取最大值再加一就是这棵树的高度 int GetTreeHeight(BN* a){ if (a == NULL) return 0;? //获取...
微信公众号：CPP进阶之旅 如果这篇文章对您有帮助，欢迎关注、评论、转发！C++ 二叉树序列化与反序列化 1、题目要求2、题目说明3、核心问题4、解题思路5、代码实现6、问题扩展7、重要说明1、题目要求 ??请实现两个函数，分别用来序列化和反序列化二叉树？ 2、题目说明 ??序列化的意思是指将一些特定的数据结构，变成有格式信息的字符串。例如对一个链表，可以将1->2->3->4->NULL序列化为"1,2,3,4"。对于序列化算法，必须支持反序列...
原题连接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/ 解题思路： 参考了Simple O(n) without map。我们可以用如下代码，打印出递归经过的所有路径： var buildTree = function (preorder, inorder) {let preorderIndex = 0;let inorderIndex = 0;let preMap = new Map();let preRealMap = new Map();function build(direction, stop) {const item = {inorderIndex, stop: ino...
牛客题目链接 1. 题目考点 根据先序和中序遍历数组重建二叉树二叉树层次遍历过程中每层最后一个节点ArrayList 转换成 int[] 2. 考点解析 递归重建二叉树，每次递归前划分对应的先序和中序数组 // 使用 Arrays.copyOfRange 截取数组 public TreeNode reBuild(int[] xianxu, int[] zhongxu) {if (xianxu.length == 0 || zhongxu.length == 0) return null;TreeNode root = new TreeNode(xianxu[0]);int i = getIndex(zhongxu, xianxu...
题目链接：LeeCode114二叉树展开为链表 题目描述： 先前序遍历将结果存到list里面，再遍历list将数据拼接到root上public static void flatten(TreeNode root) {Stack<TreeNode> nodes=new Stack<>();List<TreeNode> list=new ArrayList<>();TreeNode node=root;while (!nodes.isEmpty() || node != null) {if (node != null) {nodes.push(node);list.add(node);node=node.left;}else{node=nodes.pop();node=node.right;}}for (int ...
题目 给定一棵二叉树和其中的一个的节点，如何找出中序遍历的下一节点。树中的节点除了有两个分别指向左、右子树的指针，还有一个指向父节点的指针。 如：中序遍历序列为 {d,b,h,e,i,a,f,c,g}。问题分析 我们根据题目进行分析，要想求出其中一个树节点中序遍历的下一节点是什么，我们需要对每个单独的情况分别进行分析。 根据中序遍历的规律（先遍历左子节点，然后遍历根节点，最后遍历右子节点），下一节点可能存在的情况如下。 动...
题目链接：LeeCode104二叉树的最大深度 题目描述： dfs当节点为空代表不能向下搜索，返回当前深度回溯，返回向左搜最深的deep和向右搜最深的deep的最大值 class Solution {public static int maxDepth(TreeNode root) {return dfs(root,0);}public static int dfs(TreeNode root,int deep){if(root==null){return deep;}return Math.max(dfs(root.left, deep+1),dfs(root.right,deep+1)) ; } }
二叉树的删除操作，其中删除最小值最大值比较容易，就是一直不停的遍历二叉树的左子树和右子树，一直找到没有其左子树和右子树。然后直接将其删除就可以了 一、删除最小值（假定这个二叉树的构造是左节点小于父节点，右节点大于父节点）：从根节点开始遍历，如果有左子树就继续遍历左子树，直至没有左节点为止 代码如下 public void deleteMin() {root = deleteMin(root);}private Node deleteMin(Node x) {if (x.left == null) re...
2021.1.17 LeetCode 从零单刷个人笔记整理（持续更新） github：https://github.com/ChopinXBP/LeetCode-Babel 直接的思路是借助哈希表+DFS验证二叉树的正确性。 1.同一结点不能有两个父节点 2.有且仅有一个根节点 3.结点中不存在环 高级的一点的方法可以借助图论： 叶子结点个数 = 非叶子结点个数 + 1将所有-1看成叶子结点，也即： num(-1) = n + 1传送门：验证二叉树 You have n binary tree nodes numbered from 0 to n - 1 whe...
class Solution {public int maxDepth(TreeNode root) {// if(root==null)// return 0;// int leftHeight = maxDepth(root.left);// int rightHeight = maxDepth(root.right);// int max = (leftHeight>rightHeight? leftHeight :rightHeight)+1; // return max;if (root == null) {return 0;}Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root);int ans = 0;while (!queue.isEmpty()) {int size = queue.size...