文章目录一、题目描述1.1 题目1.2 知识点1.3 题目链接二、解题思路2.1 自研思路三、实现代码3.1 自研实现（Java）3.2 C++ 实现 一、题目描述 1.1 题目从前序与中序遍历序列构造二叉树根据一棵树的前序遍历与中序遍历构造二叉树。注意: 你可以假设树中没有重复的元素。例如，给出前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]返回如下的二叉树：3/ \9 20/ \15 71.2 知识点二叉树1.3 题目链接https://lee...
这个就是树的层次遍历，比上一题加了条件的层次遍历还要简单 只有搞清楚了各个数组之间的关系就ok 举例：三个数组只有arr中存储节点，其他两个只存储值 以下是数组变化： arr = [1]; tempArr = []; temp = 1; arr = []; tempArr = [1]; arr = [2]; arr = [2,3] res = [[1]] tempArr = []; temp = 2; tempArr = [2]; arr = [3]; temp = 3; tempArr = [2,3]; res = [[1],[2,3]]/* function TreeNode(x) {this.val = x;this.left = nu...
题目描述求一颗树的后序遍历的非递归算法 要求：必须是非递归算法，使用堆栈对象来实现 建树方法采用“先序遍历+空树用0表示”的方法 算法流程： ?? 输入第一行输入一个整数t，表示有t个测试数据 第二行起输入二叉树先序遍历的结果，空树用字符‘0’表示，输入t行 输出逐行输出每个二叉树的后序遍历结果样例输入 3 AB0C00D00 ABC00D00EF000 ABCD0000E0F00 样例输出 CBDA CDBFEA DCBFEA 提示#include<iostream> #include<stac...
题目描述请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。 1 # -*- coding:utf-8 -*-2 # class TreeNode:3 # def __init__(self, x):4 # self.val = x5 # self.left = None6 # self.right = None7 class Solution:8 def Print(self, pRoot):9 # write code here 10 if pRoot...
题目描述请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。 1 class Solution:2 def isSymmetrical(self, pRoot):3 # write code here4 def mirror(left,right):5 if left == None and right == None:6 return True7 elif left == None or right == None:8 return False9 ...
思路 如果该节点有右节点，那么它的下一个结点就是其右子树的最左节点 否则，如果他是父节点的左节点，则返回他的父节点，否则往上找，直到他的某个父节点a是a父节点的左节点，返回a的父节点。 1 class Solution:2 def GetNext(self, pNode):3 # write code here4 if pNode.right!=None:5 tmpNode = pNode.right6 while tmpNode.left:7 tmpNode=tmpNode.left8 ...
根据前序和中序重建二叉树： 1 class Solution:2 # 返回构造的TreeNode根节点3 def reConstructBinaryTree(self, pre, tin):4 # write code here5 if len(pre)==0:6 return None7 if len(pre) == 1:8 return TreeNode(pre[0])9 root = TreeNode(pre[0]) 10 tinL = tin[0:tin.index(pre[0])] 11 12 tinR = tin[tin.index(pre[0])+1:] 13 ...
//先序遍历下的第k个结点 int preorder(BTNode *t,int k,int n){int result;if(t==null) return 0;if(n==k) return t->data;result=preorder(t->lchild,k,n+1);if(result!=0) return result;else{return preorder(t->rchild,k,n+1);} }//先序中序 非递归 //中序遍历下的第k个结点 //中序遍历的第k个结点 int count=0; BTNode InOrder(BTNode *t,int k,int n){if(t==null && k<0) return null;BTNode target=null;if(t->lchild!=n...
//递归遍历二叉树 void levelOrder(BTNode *T){if(T==null) return;int height=getHeight(T);for(int i=1;i<height;i++){_levelOrder(T,i);} } void _levelOrder(BTNode *T,int num){if(T==null||i==0) return;if(i==1){visit(T->data);return;} _levelOrder(T->lchild,i-1);_levelOrder(T->rchild,i-1); }//使用栈 void levelOrder(BiTree T){Init(Queue Q);BTNode* p;EnQueue(Q,T);while(!isEmpty(Q)){DeQueue(Q,p);visit(p);...
//让树所有叶子节点连成一个单链表，让rchild作为 next指针 LNode *head=null,*pre=null;//全局变量 LNode *InOrder(BTNode *T){if(T!=null){InOrder(T->lchild);if(T->lchild==null && T->rchild==null){if(pre==null){pre=T;head=T;}else{pre->rchild=T;pre=T;}}InOrder(T->rchild);pre->rchild=null;}return head; }
题目描述输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前) 1 import copy2 class Solution:3 # 返回二维列表，内部每个列表表示找到的路径4 def FindPath(self, root, expectNumber):5 # write code here6 if root == None:7 return ...
我们希望在程序读入数据的时候，让程序稍微人性化的排序，但这里输入输出方式变动，则输出数据的顺序就会不同。（这里按照大小顺序） 代码如下#include <iostream> using namespace std; struct Std {int iNum;struct Std *Lnext;struct Std *Rnext; }; struct Std *Forse()//创建空树 {struct Std *Head;Head=new Std;(*Head).iNum=0;Head->Lnext=NULL;Head->Rnext=NULL;return Head; } void Map(struct Std *Head,int n)//插入数...
题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。解题：链接：https://www.nowcoder.com/questionTerminal/8a19cbe657394eeaac2f6ea9b0f6fcf6?answerType=1&f=discussion 来源：牛客网/*** Definition for binary tree* public class TreeNode {* int v...
题目描述操作给定的二叉树，将其变换为源二叉树的镜像。 1 class Solution:2 # 返回镜像树的根节点3 def Mirror(self, root):4 # write code here5 if root==None:6 return None7 #处理根节点8 root.left,root.right=root.right,root.left9 #处理左子树 10 self.Mirror(root.left) 11 #处理右子树 12 self.Mirror(root.right)2019-12...
检查两个二叉树本质上是同构的算法是什么？我的代码-boolean isIsomorphic(Root t1 , Root t2){if(t1==null || t2==null){return false;}if((t1.value == t2.value) && (isIsomorphic(t1.left,t2.right) && isIsomorphic(t1.right,t2.left))) {return true}return false; }解决方法:wikipedia article for ‘isomorphism’说：“如果两个对象是同构的,那么由同构保留的并且其中一个对象为真的任何属性也对另一个对象也为真”. 因此...