公司网站域名如何备案,优购物官方网站购物,wordpress 媒体库缩略图生成,wordpress4.0安装教程【本节目标】 1. 掌握树的基本概念 2. 掌握二叉树概念及特性 3. 掌握二叉树的基本操作 4. 完成二叉树相关的面试题练习 一. 树型结构
1 概念★ 树是一种 非线性 的数据结构#xff0c;它是由 n #xff08; n0 #xff09;个有限结点组成一个具有层次关系的集…【本节目标】 1. 掌握树的基本概念 2. 掌握二叉树概念及特性 3. 掌握二叉树的基本操作 4. 完成二叉树相关的面试题练习 一. 树型结构
1 概念★ 树是一种 非线性 的数据结构它是由 n n0 个有限结点组成一个具有层次关系的集合。 把它叫做树是因为它看 起来像一棵倒挂的树也就是说它是根朝上而叶朝下的 。它具有以下的特点 有一个特殊的结点称为根结点根结点没有前驱结点 除根结点外其余结点被分成M(M 0)个互不相交的集合T1、T2、......、Tm其中每一个集合Ti (1 i m) 又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱可以有0个或多个后继树是递归定义的 注意树形结构中子树之间不能有交集否则就不是树形结构 2 概念★★★ 结点的度一个结点含有子树的个数称为该结点的度 如上图A的度为6 树的度一棵树中所有结点度的最大值称为树的度 如上图树的度为6 叶子结点或终端结点度为0的结点称为叶结点 如上图B、C、H、I...等节点为叶结点 双亲结点或父结点若一个结点含有子结点则这个结点称为其子结点的父结点 如上图A是B的父结点 孩子结点或子结点一个结点含有的子树的根结点称为该结点的子结点 如上图B是A的孩子结点 根结点一棵树中没有双亲结点的结点如上图A 结点的层次从根开始定义起根为第1层根的子结点为第2层以此类推 树的高度或深度树中结点的最大层次 如上图树的高度为4 树的以下概念只需了解在看书时只要知道是什么意思即可 非终端结点或分支结点度不为0的结点 如上图D、E、F、G...等节点为分支结点 兄弟结点具有相同父结点的结点互称为兄弟结点 如上图B、C是兄弟结点 堂兄弟结点双亲在同一层的结点互为堂兄弟如上图H、I互为兄弟结点 结点的祖先从根到该结点所经分支上的所有结点如上图A是所有结点的祖先 子孙以某结点为根的子树中任一结点都称为该结点的子孙。如上图所有结点都是A的子孙 森林由mm0棵互不相交的树组成的集合称为森林 3 树的表示形式★ 树结构相对线性表就比较复杂了要存储表示起来就比较麻烦了实际中树有很多种表示方式如 双亲表示法 孩子表示法 、 孩子双亲表示法 、 孩子兄弟表示法 等等。我们这里就简单的了解其中最常用的 孩子兄弟表示法 。 class Node { int value ; // 树中存储的数据 Node firstChild ; // 第一个孩子引用 Node nextBrother ; // 下一个兄弟引用 } 4 树的应用 文件系统管理目录和文件 二. 二叉树★★★
1 概念 一棵二叉树是结点的一个有限集合该集合 1. 或者为空 2. 或者是由 一个根节 点加上两棵别称为 左子树 和 右子树 的二叉树组成。 从上图可以看出 1. 二叉树不存在度大于 2 的结点 2. 二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树 注意对于任意的二叉树都是由以下几种情况复合而成的 大自然的奇观 2 两种特殊的二叉树 1. 满二叉树 : 一棵二叉树如果 每层的结点数都达到最大值则这棵二叉树就是满二叉树 。也就是说 如果一棵 二叉树的层数为 K且结点总数是 2^K-1则它就是满二叉树 。 2. 完全二叉树 : 完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为 K 的有 n个结点的二叉树当且仅当其每一个结点都与深度为K 的满二叉树中编号从 0 至 n-1的结点一一对应时称之为完 全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。 3 二叉树的性质 1. 若规定 根结点的层数为 1 则一棵 非空二叉树的第i层上最多有 2^i-1) (i0) 个结点 2. 若规定只有 根结点的二叉树的深度为 1 则 深度为 K的二叉树的最大结点数是 2^k-1 (k0) 3. 对任何一棵二叉树 , 如果其 叶结点个数为 n0, 度为 2 的非叶结点个数为 n2, 则有 n0n21 一棵N个节点的树可以产生N-1条边 n0:产生不了边 n1:产生n1条边 n2:产生2*n2条边 n12*n2N-1 ----对于边 n0n1n2N- ---对于点 联合方程则 n0n21 4. 具有 n 个结点的完全二叉树的深度 k 为 log2(n1) 上取整 5. 对于具有 n 个结点的完全二叉树 如果按照 从上至下从左至右的顺序对所有节点从 0 开始编号 则对于 序号为 i 的结点有 若i0双亲序号(i-1)/2i0i为根结点编号无双亲结点 若2i1n左孩子序号2i1否则无左孩子 若2i2n右孩子序号2i2否则无右孩子 1. 某二叉树共有 399 个结点其中有 199 个度为 2 的结点则该二叉树中的叶子结点数为 A 不存在这样的二叉树 B 200 C 198 D 199 2. 在具有 2n 个结点的完全二叉树中叶子结点个数为 A n B n1 C n-1 D n/2 3. 一个具有 767 个节点的完全二叉树其叶子节点个数为 A 383 B 384 C 385 D 386 4. 一棵完全二叉树的节点数为 531 个那么这棵树的高度为 A 11 B 10 C 8 D 12 答案 1.B n0n21199-1198 2.A结点数为偶数个则度为1的结点为1结点数为奇数个则度为1的结点为0度为2的为x-1个度为0的为x。本题为xx-112nxn 3.B 4.B 4 二叉树的存储 二叉树的存储结构 分为 顺序存储 和 类似于链表的链式存储 。 二叉树的链式存储是通过一个一个的节点引用起来的常见的表示方式有二叉和三叉表示方式 具体如下 static class TreeNode{public char val;public TreeNode left;public TreeNode right;public TreeNode(char val) {this.val val;}}
孩子双亲表示法后序在平衡树位置介绍本文采用孩子表示法来构建二叉树。 5 二叉树的基本操作
(1) 前置说明 再看二叉树基本操作前再回顾下二叉树的概念二叉树是 1. 空树 2. 非空根节点根节点的左子树、根节点的右子树组成的 从概念中可以看出二叉树定义是递归式的因此后序基本操作中基本都是按照该概念实现的。 (2)二叉树的遍历 a. 前中后序遍历 学习二叉树结构最简单的方式就是遍历。所谓遍历 (Traversal) 是指沿着某条搜索路线依次对树中每个结 点均做一次且仅做一次访问 。 访问结点所做的操作依赖于具体的应用问题 ( 比如打印节点内容、节点内容加 1) 。 遍历是二叉树上最重要的操作之一是二叉树上进行其它运算之基础。 在遍历二叉树时如果没有进行某种约定每个人都按照自己的方式遍历得出的结果就比较混乱如果按 照某种规则进行约定则每个人对于同一棵树的遍历结果肯定是相同的 。 如果N 代表根节点 L 代表根节点的左子树R 代表根节点的右子树则根据遍历根节点的先后次序有以下遍历方式 NLR前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点---根的左子树---根的右子树。 LNR中序遍历(Inorder Traversal)——根的左子树---根节点---根的右子树。 LRN后序遍历(Postorder Traversal)——根的左子树---根的右子树---根节点。 // 前序遍历 void preOrder ( Node root ); // 中序遍历 void inOrder ( Node root ); // 后序遍历 void postOrder ( Node root ); void preOrder(TreeNode root) {if(rootnull){return;}else {char ch root.val;System.out.print(ch );preOrder(root.left);preOrder(root.right);}}// 中序遍历void inOrder(TreeNode root) {if(rootnull){return;}else {char ch root.val;preOrder(root.left);System.out.print(ch );preOrder(root.right);}}// 后序遍历void postOrder(TreeNode root) {if(rootnull){return;}else {char ch root.val;preOrder(root.left);preOrder(root.right);System.out.print(ch );}}/*** Definition for a binary tree node.* 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;* }* }*/
class Solution {ListInteger listnew LinkedList();public ListInteger preorderTraversal(TreeNode root) {ListInteger listnew LinkedList();if(rootnull){return list;}else{list.add(root.val);}ListInteger list1 preorderTraversal(root.left);list.addAll(list1);ListInteger list2 preorderTraversal(root.right);list.addAll(list2);return list;}
}
以下为前序遍历的图解 前序遍历结果 1 2 3 4 5 6 中序遍历结果 3 2 1 5 4 6 后序遍历结果 3 1 5 6 4 1 b. 层序遍历 层序遍历 除了先序遍历、中序遍历、后序遍历外还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1 层序遍历就是从所在二叉树的根节点出发首先访问第一层的树根节点然后从左到右访问第 2 层上的节点接着是第三层的节点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历。 【练习】根据以上二叉树的三种遍历方式给出以下二叉树的 前序遍历结果 ABDEHCFG 中序遍历结果 DBEHAFCG 后序遍历结果 DHEBFGCA 选择题 1. 某完全二叉树按层次输出同一层从左到右的序列为 ABCDEFGH 。该完全二叉树的前序序列为 ( ) A: ABDHECFG B: ABCDEFGH C: HDBEAFCG D: HDEBFGCA 2. 二叉树的先序遍历和中序遍历如下先序遍历 EFHIGJK; 中序遍历 HFIEJKG. 则二叉树根结点为 ( ) A: E B: F C: G D: H 3. 设一课二叉树的中序遍历序列 badce 后序遍历序列 bdeca 则二叉树前序遍历序列为 ( ) A: adbce B: decab C: debac D: abcde 4. 某二叉树的后序遍历序列与中序遍历序列相同均为 ABCDEF 则按层次输出 ( 同一层从左到右 ) 的序列为 () A: FEDCBA B: CBAFED C: DEFCBA D: ABCDEF 【参考答案】 1.A 2.A 3.D 4.A (3 二叉树的基本操作 // 获取树中节点的个数 int size ( Node root ); // 获取叶子节点的个数 int getLeafNodeCount ( Node root ); // 获取第 K 层节点的个数 int getKLevelNodeCount ( Node root , int k ); // 获取二叉树的高度 int getHeight ( Node root ); // 检测值为 value 的元素是否存在 Node find ( Node root , int val ); // 层序遍历 void levelOrder ( Node root ); // 判断一棵树是不是完全二叉树 boolean isCompleteTree ( Node root ); 1.节点个数 //只要节点不为空那么就count //只要节点不为空那么就countpublic static int count0;public void size(TreeNode root) {if(rootnull){return ;}else{count;size(root.left);size(root.right);}} //整棵树有多少个结点左子树有多少个结点右子树有多少个结点1 public int size(TreeNode root) {if(rootnull){return 0;}return size(root.left)size(root.right)1;
} 2.叶子节点的个数 //只要是叶子结点那么就count public static int count0;public void getLeafNodeCount(TreeNode root){if(rootnull){return ;}if(root.leftnullroot.rightnull){count;}getLeafNodeCount(root.left);getLeafNodeCount(root.right);} //整棵树有多少个叶子结点左子树有多少个叶子结点右子树有多少个叶子结点 public int getLeafNodeCount(TreeNode root){if(rootnull){return 0;}if(root.leftnullroot.rightnull){return 1;}return getLeafNodeCount(root.left)getLeafNodeCount(root.right);} 3.第K层节点的个数 第k层结点个数左子树的第k-1层结点个数右子树的第k-1层结点个数 public int getKLevelNodeCount(TreeNode root,int k){if(rootnull){return 0;}if(k1){return 1;}return getKLevelNodeCount(root.left,k-1)getKLevelNodeCount(root.right,k-1);} 4.二叉树的高度 二叉树的高度左右子树高度的最大值1 时间复杂度O(N)空间复杂度O(logN) public int maxDepth(TreeNode root) {if(rootnull){return 0;}int leftHeightmaxDepth(root.left);int rightHeightmaxDepth(root.right);return Math.max(leftHeight,rightHeight)1;// return (leftHeightrightHeight?leftHeight1:rightHeight1);
} 5.value的元素是否存在 如果根节点是则返回根节点不是则向左子树遍历左子树不是则向右子树遍历左右子树都不是则返回空 时间复杂度O(N)空间复杂度O(logN) public TreeNode find(TreeNode root, int val){if(rootnull){return null;}if(root.valval){return root;}TreeNode leftNodefind(root.left,val);if(leftNode!null){return leftNode;}TreeNode rightNodefind(root.right,val);if(rightNode!null){return rightNode;}return null;} 6.层序遍历 /*** Definition for a binary tree node.* 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;* }* }*/
class Solution {public ListListInteger levelOrder(TreeNode root) {ListListInteger listnew ArrayList();if(rootnull){return list;}TreeNode curroot;QueueTreeNode queuenew LinkedList();queue.offer(root);while(!queue.isEmpty()){ListInteger list2new ArrayList();int sizequeue.size();while(size0){ curqueue.poll();list2.add(cur.val);if(cur.left!null){queue.offer(cur.left);}if(cur.right!null){queue.offer(cur.right);}size--;} list.add(list2) ;}return list; }
} 7.完全二叉树判断 利用队列如果在弹出值为null时查看当前queue内的值如果全部是null则是完全二叉树否则不是完全二叉树 import java.util.*;/** public class TreeNode {* int val 0;* TreeNode left null;* TreeNode right null;* public TreeNode(int val) {* this.val val;* }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param root TreeNode类 * return bool布尔型*/public boolean isCompleteTree (TreeNode root) {if(rootnull){return true;}QueueTreeNode queuenew LinkedList();TreeNode curroot;queue.offer(root);while(!queue.isEmpty()){curqueue.poll();if(cur!null){queue.offer(cur.left);queue.offer(cur.right);}else{break;} }int sizequeue.size();while(size0){TreeNode nowqueue.poll();if(now!null){return false;}size--;} return true; }
} 三、 二叉树相关oj题 1. 检查两颗树是否相同。 1.判断结构是否一样左右子树要么同为空要么同不为空2.左右子树同为null则正确3.判断值是否一样4.判断左子树右子树是否一样时间复杂度O(min(M,N)) /*** Definition for a binary tree node.* 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;* }* }*/
class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {//1.判断结构是否一样if((p!nullqnull)||(pnullq!null)){return false;}//上述运行后通过的要么同为空要么同不为空//同为空则正确if(pnullqnull){return true;}//2.判断值是否一样if(p.val!q.val){return false;}//3.判断左子树右子树是否一样return isSameTree(p.left, q.left)isSameTree(p.right, q.right);}
} 2. 另一颗树的子树。 当前子树和根节点是否一样当前子树和根节点左子树是否一样当前子树和根节点右子树是否一样时间复杂度O(M*N) /*** Definition for a binary tree node.* 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;* }* }*/
class Solution {public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(rootnull){return false;}if(isSameTree(root, subRoot)){return true;}if(isSubtree(root.left, subRoot)){return true;} if(isSubtree(root.right, subRoot)){ return true;} return false;}public boolean isSameTree(TreeNode p, TreeNode q) {//1.判断结构是否一样if((p!nullqnull)||(pnullq!null)){return false;}//上述运行后通过的要么同为空要么同不为空//同为空则正确if(pnullqnull){return true;}//2.判断值是否一样if(p.val!q.val){return false;}//3.判断左子树右子树是否一样return isSameTree(p.left, q.left)isSameTree(p.right, q.right);}
} 3. 翻转二叉树。 /*** Definition for a binary tree node.* 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;* }* }*/
class Solution {public TreeNode invertTree(TreeNode root) {if(rootnull){return null;}TreeNode tmproot.left;root.leftroot.right;root.righttmp;invertTree(root.left);invertTree(root.right);return root;}
} 4. 判断一颗二叉树是否是平衡二叉树。 时间复杂度O(N^2) /*** Definition for a binary tree node.* 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;* }* }*/
class Solution {public boolean isBalanced(TreeNode root) {if(rootnull){return true;}int leftheightgetheight(root.left);int rightheightgetheight(root.right);return Math.abs(leftheight-rightheight)2isBalanced(root.left)isBalanced(root.right);/* if(Math.abs(leftheight-rightheight)2){return false;}if(isBalanced(root.left)isBalanced(root.right)){return true;}return false;*/}public int getheight(TreeNode root){if(rootnull){return 0;}int leftheightgetheight(root.left);int rightheightgetheight(root.right);return Math.max(leftheight,rightheight)1;}
} 时间复杂度O(N) /*** Definition for a binary tree node.* 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;* }* }*/
class Solution {public boolean isBalanced(TreeNode root) {if(rootnull){return true;}return getheight(root)0;}public int getheight(TreeNode root){if(rootnull){return 0;}int leftheightgetheight(root.left);if(leftheight0){return -1;}int rightheightgetheight(root.right);if(Math.abs(leftheight-rightheight)1rightheight0){return Math.max(leftheight,rightheight)1;}else{return -1;}}
} 5. 对称二叉树。 root的左子树和root的右子树是否对称 /*** Definition for a binary tree node.* 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;* }* }*/
class Solution {public boolean isSymmetric(TreeNode root) {if(rootnull){return true;}return isSymmetricChild(root.left,root.right);}public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree){//判断结构一样if((leftTreenullrightTree!null)||(leftTree!nullrightTreenull)){return false;}//左右同为空或者左右同不为空if(leftTreenullrightTreenull){return true;}if(leftTree.val!rightTree.val){return false;}return isSymmetricChild(leftTree.left,rightTree.right)isSymmetricChild(leftTree.right,rightTree.left);}} 6. 二叉搜索树和双向链表 二叉搜索树的特点中序遍历是有序的 import java.util.*;
/**
public class TreeNode {int val 0;TreeNode left null;TreeNode right null;public TreeNode(int val) {this.val val;}}
*/
public class Solution {TreeNode prev null;public TreeNode Convert(TreeNode pRootOfTree) {if(pRootOfTreenull){return null;}ConvertChild(pRootOfTree);TreeNode headpRootOfTree;while(head.left!null){headhead.left;}return head;}public void ConvertChild(TreeNode root) {if (root null) {return;}ConvertChild(root.left);root.left prev;if (prev ! null) {prev.right root;}prev root;ConvertChild(root.right);}
}7.二叉树的构建及遍历。 import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {static class TreeNode{public char val;public TreeNode left;public TreeNode right;public TreeNode(char ch) {this.valch;}
}public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseString strin.nextLine();TreeNode root createTree(str);Inorder(root);}}public static int i0;public static TreeNode createTree(String str){TreeNode rootnull;if(str.charAt(i)!#){rootnew TreeNode(str.charAt(i));i;root.leftcreateTree(str);root.rightcreateTree(str);}else{i;}return root;}public static void Inorder(TreeNode root){if(rootnull){return;}Inorder(root.left);System.out.print(root.val );Inorder(root.right);}
} 8. 二叉树的分层遍历 。 使用队列来辅助分层遍历 /*** Definition for a binary tree node.* 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;* }* }*/
class Solution {public ListListInteger levelOrder(TreeNode root) {ListListInteger listnew ArrayList();if(rootnull){return list;}TreeNode curroot;QueueTreeNode queuenew LinkedList();queue.offer(root);while(!queue.isEmpty()){ListInteger list2new ArrayList();int sizequeue.size();while(size0){ curqueue.poll();list2.add(cur.val);if(cur.left!null){queue.offer(cur.left);}if(cur.right!null){queue.offer(cur.right);}size--;} list.add(list2) ;}return list; }
} 9. 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先 。 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(rootnull){return null;}if(rootp||rootq){return root;}TreeNode leftnodelowestCommonAncestor(root.left, p, q);TreeNode rightnodelowestCommonAncestor(root.right, p, q);if(leftnodenull){return rightnode;}else if(rightnodenull){return leftnode;}else{return root;}}
} 利用前面的把二叉树改成双向链表的思路可以把距离父节点远的向父节点靠近 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(rootnull){return null;}StackTreeNode stackpnew Stack();StackTreeNode stackqnew Stack();getPath(root,p,stackp);getPath(root,q,stackq);int sizepstackp.size();int sizeqstackq.size();int size0;if(sizepsizeq){sizesizep-sizeq;while(size!0){stackp.pop();size--;}}else{sizesizeq-sizep;while(size!0){stackq.pop();size--;}}while(!stackp.isEmpty()!stackq.isEmpty()){if(stackp.peek()!stackq.peek()){stackp.pop();stackq.pop();}else{return stackp.pop();}}return null;// if(rootnull){// return null;// }// if(rootp||rootq){// return root;// }// TreeNode leftnodelowestCommonAncestor(root.left, p, q);// TreeNode rightnodelowestCommonAncestor(root.right, p, q);// if(leftnodenull){// return rightnode;// }else if(rightnodenull){// return leftnode;// }else{// return root;// }}public boolean getPath(TreeNode root,TreeNode p,StackTreeNode stack){if(rootnull){return false;}stack.push(root);if(rootp){return true;}boolean leftpathgetPath(root.left,p,stack);if(leftpath){return true;}boolean rightpathgetPath(root.right,p,stack);if(rightpath){return true;}stack.pop();return false;}
} 10. 根据一棵树的前序遍历与中序遍历构造二叉树。 /*** Definition for a binary tree node.* 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;* }* }*/
class Solution {public int preIndex;public TreeNode buildTree(int[] preorder, int[] inorder) {return buildTreeChild(preorder, inorder,0,inorder.length-1);}public TreeNode buildTreeChild(int[] preorder,int[] inorder,int inBegin, int inEnd) {//表示没有子树了if(inBegininEnd){return null;}TreeNode rootnew TreeNode(preorder[preIndex]);//将首元素作为根节点int midindexfindVal(inorder,inBegin,inEnd,preorder[preIndex]);preIndex;root.leftbuildTreeChild(preorder,inorder,inBegin,midindex-1);root.rightbuildTreeChild(preorder,inorder, midindex1,inEnd);return root;}private int findVal(int[] inorder,int inBegin, int inEnd,int val){for(int iinBegin;iinEnd;i){if(inorder[i]val){return i;}}return -1;}
} 11. 根据一棵树的中序遍历与后序遍历构造二叉树。 /*** Definition for a binary tree node.* 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;* }* }*/
class Solution {public int postIndex;public TreeNode buildTree(int[] inorder, int[] postorder) {postIndexpostorder.length-1;return buildTreeChild(inorder,postorder,0,inorder.length-1);}public TreeNode buildTreeChild(int[] inorder, int[] postorder,int inBegin,int inEnd) {if(inBegininEnd){return null;}TreeNode rootnew TreeNode(postorder[postIndex]);int findindexfindVal(inorder,inBegin,inEnd,postorder[postIndex]);postIndex--;root.rightbuildTreeChild(inorder,postorder,findindex1,inEnd); root.leftbuildTreeChild(inorder,postorder,inBegin,findindex-1); return root;}private int findVal(int[] inorder,int inBegin,int inEnd,int val){for(int iinBegin;iinEnd;i){if(inorder[i]val){return i;} }return -1;}
} 12. 二叉树创建字符串。 /*** Definition for a binary tree node.* 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;* }* }*/
class Solution {public String tree2str(TreeNode root) {StringBuilder stringBuilder new StringBuilder();tree2strChild(root,stringBuilder);return stringBuilder.toString();}public void tree2strChild(TreeNode t,StringBuilder stringBuilder) {if(tnull){return;}stringBuilder.append(t.val);if(t.left!null){stringBuilder.append(();tree2strChild(t.left,stringBuilder); stringBuilder.append());}else{if(t.rightnull){return;}else{stringBuilder.append(();stringBuilder.append());}}if(t.right!null){stringBuilder.append(();tree2strChild(t.right,stringBuilder); stringBuilder.append());}else{return;}}
} 13. 二叉树前序非递归遍历实现 /*** Definition for a binary tree node.* 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;* }* }*/
class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger listnew LinkedList();StackTreeNode stacknew Stack();TreeNode curroot;while(cur!null||!stack.isEmpty()){while(cur!null){stack.push(cur);list.add(cur.val);curcur.left;}TreeNode topstack.pop();curtop.right;}return list;}
} 14. 二叉树中序非递归遍历实现。 /*** Definition for a binary tree node.* 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;* }* }*/
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger listnew LinkedList();StackTreeNode stacknew Stack();TreeNode curroot;while(cur!null||!stack.isEmpty()){while(cur!null){stack.push(cur);curcur.left;}TreeNode topstack.pop();list.add(top.val);curtop.right;}return list;}
} 15. 二叉树后序非递归遍历实现。 /*** Definition for a binary tree node.* 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;* }* }*/
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger listnew LinkedList();StackTreeNode stacknew Stack();TreeNode curroot;while(cur!null||!stack.isEmpty()){while(cur!null){stack.push(cur);curcur.left;}TreeNode topstack.peek();if(top.rightnull||list.contains(top.right.val)){topstack.pop();list.add(top.val);}else{curtop.right;}}return list;}} /*** Definition for a binary tree node.* 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;* }* }*/
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger listnew LinkedList();StackTreeNode stacknew Stack();TreeNode curroot;TreeNode prevnull;while(cur!null||!stack.isEmpty()){while(cur!null){stack.push(cur);curcur.left;}TreeNode topstack.peek();if(top.rightnull||top.rightprev){list.add(top.val);topstack.pop();prevtop;}else{curtop.right;}}return list;}} if(top.rightnull||top.rightprev){//防止不停的在右子树和根子树之间不停循环 list.add(top.val); topstack.pop(); prevtop; }else{ curtop.right; }
