题目描述 操作给定的二叉树，将其变换为源二叉树的镜像。 输入描述： 二叉树的镜像定义：源二叉树 8/ 6 10/ \ / 5 7 9 11镜像二叉树8/ 10 6/ \ / 11 9 7 5题目分析 通过图可以看出，要想使二叉树变换为源二叉树的镜像，我们可以让每个节点的左右节点互换位置，可以使用递归，要使一个节点的左右节点交换位置，先使该节点的子节点的左右节点交换位置，一直到子节点为空。 Java实...
题目描述 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。 题目分析 可以使用递归，每次将左右两颗子树当成新的子树进行处理，中序的左右子树索引很好找，前序的开始结束索引通过计算中序中左右子树的大小来计算，然后递归求解，直到startPre>endP...
/** @lc app=leetcode.cn id=104 lang=c** [104] 二叉树的最大深度** https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/description/** algorithms* Easy (67.34%)* Total Accepted: 33.2K* Total Submissions: 49.2K* Testcase Example: [3,9,20,null,null,15,7]** 给定一个二叉树，找出其最大深度。* * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。* * 说明: 叶子节点是指没有子节点的节点。* ...
二叉树的应用很广，比如红黑树（特殊的二叉树)，数据库的B+tree，以及一些压缩算法 这里只介绍简单的二叉树: 特征：一.一个根节点 二.众多子节点，每个节点最多有两个子节点 二叉树遍历方式：总体有两种，分别基于DFS(深度优先搜索)和BFS(广度优先搜索)的，前者包括递归(先序、中序、后序)和Stack(栈)，后者是队列实现的层序遍历。 ####树节点类如下public class TreeNode {private int data;private TreeNode left;p...
二叉树中序非递归遍历算法： 先将左子树放进栈中，无左子树时出栈，从右子树开始，继续对右子树循环。 代码如下: void inOrder2(BinTree *root) //非递归中序遍历2 {3 stack<BinTree*> s;4 BinTree *p=root;5 while(p!=NULL||!s.empty())6 {7 while(p!=NULL)8 {9 s.push(p); 10 p=p->lchild; 11 } 12 i...
题目：输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。 思路：利用二叉树的前序遍历，把每一个遍历到是根节点保存在一个 list 中。然后判断当前节点是不是叶节点，若不是叶节点，则用递归的方式接着遍历它的左节点和右节点； 若是叶节点则判断从根节点到这个叶节点的路径和等不等于 target，如果相等就把这条路径对应的 list 添加...
题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。 思路：利用中序遍历的方法递归遍历二叉树，把二叉树拆分为左子树、根节点、右子树三部分，再连接起来。第一步先遍历左子树转化为链表，然后把根节点连在左子树的最后节点，然后再递归遍历右子树。 测试用例： 1. 功能测试：完全二叉树；所有节点只有左子树的二叉树；所有节点只有右子树的二叉树；只有...
从上往下打印二叉树思路实现 思路 可以借助队列先进先出的特点， ①每次取对头节点的值放入结果中 ②按照先序遍历每次先将根节点存入，再依次存入其左孩子右孩子（如果有的话） 以上两点在while循环中实现，直至队列长度为0 实现 # -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution:# 返回从上到下每个节点值...
记录一下某次使用平衡二叉树。 注：二叉树概念 【 1、二叉树、完全二叉树、满二叉树、平衡二叉树区别 二叉树： 除了叶子节点外，每个节点只有两个分支，左子树和右子树，每个节点的最大度数为2 满二叉树：除了叶结点外每一个结点都有左右子叶 且 叶结点都处在最底层的二叉树。 完全二叉树：只有最下面的两层结点度小于2，并且最下面一层的结点都集中再该层最左边的若干位置的二叉树 -- 满二叉树一定是完全二叉树，完全二叉树不一定...
递归和非递归方法中序遍历二叉树 Leetcode题 递归方法：# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution(object):def inorderTraversal(self, root):""":type root: TreeNode:rtype: List[int]"""ans = []if root==None:return ansself.inTraverse(root, ans)return ansdef inTrave...
题意： 给定一个二叉树，返回它的后序遍历。 示例： 输入: [1,null,2,3] 12/3 输出: [3,2,1]中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。若二叉树为空则结束返回，否则： （1）后序遍历左子树 （2）后序遍历右子树 （3）访问根结点 方法一： 递归 class Solution:def postorderTraversal(self, root: TreeNode) -> List[int]:if root == None:return []res = []res += self.postorderTraversal(root.left)res += s...
解题思路 将当前节点的左子树和右子树交换 递归实现 下面是java代码实现 public class Solution {public void Mirror(TreeNode root) {if(root == null) {return;}swap(root);Mirror(root.left);Mirror(root.right);}private void swap(TreeNode node) {TreeNode temp = node.left;node.left= node.right;node.right = temp;} }
准备面试，撸了个二叉树python的代码，最后有代码，记录梳理下写的思路： 目录 1-利用add创建一个二叉树 2-查询树的节点数 3-查询树的深度 4-前序遍历 5-中序遍历 6-后序遍历 7-层次遍历 8-查询叶子节点数 实验结果 1-利用add创建一个二叉树这里只做了按照完全二叉树进行构建树，之后会想想办法试着写一个支持非完全二叉树的(还没有思路) 核心思想：设定一个根节点，先设定左子节点在设定右子节点，设定完后表明该层任务结束，在新...
从根结点开始，将所有最左结点全部压栈，每当一个结点出栈时，都先扫描该结点的右子树，只有当一个结点的左孩子和右孩子结点均被访问过了，才能访问结点自身。 非递归算法实现如下：struct TreeNode {int val;TreeNode *left;TreeNode * right;TreeNode(int x) : val(x), left(NULL), right(NULL) {} };vector<int> postorderTraversal(TreeNode* root) {vector<int> path;stack<TreeNode *> st;TreeNode * pre = NULL;bool left...
题目描述 从上往下打印出二叉树的每个节点，同层节点从左至右打印。 解答 /* struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {} };*/ class Solution { public:vector<int> PrintFromTopToBottom(TreeNode* root) {vector<int> result;if(NULL == root)return result;queue<TreeNode*> q;q.push(root);while(!q.empty()){TreeNode* temp=q.front();res...