赞
踩
1.或者为空
2.或者是由一个根节点加上两颗分别为左子树 右子树的二叉树组成
1.若规定根节点的层数为1,则一颗非空二叉树的第i层最多有2^(i-1) 个结点(i大于零)
2.若规定只有根节点的二叉树的深度为1,则深度为k的二叉树的最大结点数为2^k - 1 (k>=0)
3.对任何一颗二叉树,如果其叶结点个数为n0,度为2的非叶节点的个数为n2 ,则有n0 = n2 +1
4.具有n个节点的完全二叉树的深度为log2(n+1)上取整
5.具有n个节点的完全二叉树,如果按照从上至下 从左至右的顺序对所有节点从0开始编号,则对于序号为i的节点有:
若 i > 0 ,双亲序号:(i-1)/ 2 ,若i=0则i为根节点编号
若2i+1<n,左孩子序号:2i+1,否则无左孩子
若2i+2<n,右孩子序号为2i+2,否则无右孩子
需要注意的是节点个数为奇数个的完全二叉树没有度为1的节点,如下图
如果两个树在结构上相同,并且节点具有相同的值,则认为他们是相同的
思路:先判断pq是否为空,若一个为空一个不为空,则必定不一样,返回false,若均为空,则视为相同,返回true,若均不为空,则用递归的思想 继续判断左子树和右子树是否相同
- class Solution{
- public boolean isSameTree(TreeNode p,TreeNode q){
- if (p != null && q == null || p==null && q!= null) {
- return false;//结构不一样
- }
- if (p==null&&q==null)return true;//两个都为空,相同
- if (p.val!=q.val){//两个均不为空,继续比较
- return false;
- }
- //上述代码完成走到这里说明 p!= null && q != null && 根节点的值一致
- return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
- }
- }
给出root 和 subRoot 检验root中是否包含与subRoot相同的结构和节点值的子树,如果存在返回true,否则返回false
root的每一个节点和subRoot中每一个节点比较一次,看是否相同,若m n 分别为两棵树的节点个数,则时间复杂度为m*n
- class Solution2{
- public boolean isSubtree(TreeNode rood,TreeNode subRoot){
- if (rood == null)return false;
- if (isSameTree(rood,subRoot)){
- return true;
- }
- if (isSameTree(rood.left,subRoot)){
- return true;
- }
- if (isSameTree(rood.right,subRoot)){
- return true;
- }
- return false;
- }
- public boolean isSameTree(TreeNode p,TreeNode q){
- if (p != null && q == null || p==null && q!= null) {
- return false;//结构不一样
- }
- if (p==null&&q==null)return true;//两个都为空,相同
- if (p.val!=q.val){//两个均不为空,继续比较
- return false;
- }
- //上述代码完成 走到这里说明 p!= null && q != null && 根节点的值一致
- return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
- }
- }
思路:首先判断二叉树是否为空,若为空则返回false,若树不为空,则递归交换根节点root的左子树和右子树
- class Solution3 {
- public TreeNode changeNode(TreeNode root){
- if ((root.right==null&&root.left!=null) ||(root.right!= null&&root.left==null))
- return root;
- if (root == null)return null;
- TreeNode tmp = new TreeNode('a');
- tmp = root.left;
- root.left = root.right;
- root.right = tmp;
- caculateSize(root.left);
- caculateSize(root.right);
- return root;
- }
- }
- }
给定一个二叉树,判断他是否是高度平衡的二叉树(一个二叉树每个节点的左右两个子树的高度的绝对值不超过1)
- class Solution{
- public boolean isBalance(TreeNode root){
- if (root == null){
- return true;
- }
- int leftH = getHeight(root.left);
- int rightH = getHeight(root.right);
- if (Math.abs(leftH - rightH)<2 && isBalance(root.right) && isBalance(root.left)){
- return true;
- }
- return false;
- }
- }
- class Solution5{//判断是否是平衡二叉树
- public int isBalance(TreeNode root){
- if (root == null){
- return 0;
- }
- int leftH = getHeight(root.left);
- int rightH = getHeight(root.right);
- //不平衡则返回负数
- if (leftH>=0 && rightH>=0 && Math.abs(leftH - rightH)<=0){
- return Math.max(rightH,leftH)+1;
- }else return -1;
- }
- }
- class Solution5{//判断是否是平衡二叉树
- public int isBalance(TreeNode root){
- if (root == null){
- return 0;
- }
- int leftH = getHeight(root.left);
- if (leftH < 0){
- return -1;
- }
- int rightH = getHeight(root.right);
- //不平衡则返回负数
- if (leftH>=0 && rightH>=0 && Math.abs(leftH - rightH)<=0){
- return Math.max(rightH,leftH)+1;
- }else return -1;
- }
- }
2.1使用非递归的方法,使用队列进行操作,首先root指针指向根节点,判断是否有左右孩子,若有,则将左右孩子按照从左往右的顺序依次入队,再对root进行出队打印,第一次出队root指向根节点,第二次出队的root更新为root.right,同时判断root是否有左右孩子,若有,任然按照从左至右的顺序入队,再对root出队打印,以此往复
- public void leveOrder(treeNode root){
- if (root == null)return;
- Queue<treeNode> queue = new LinkedList<>();
- queue.offer(root);
- while (!queue.isEmpty()){
- treeNode cur = queue.poll();
- System.out.println(cur.val + " ");
- if (cur.left != null){
- queue.offer(cur.left);
- }
- if (cur.right != null){
- queue.offer(cur.right);
- }
- }
- }
- public List<List<Character>> levelOrder2(treeNode root){
- List<List<Character>> listList = new ArrayList<>();
- if (root == null)return listList;
- Queue<treeNode> queue = new LinkedList<>();//申请一个队列用于存放树的每一个节点
- queue.offer(root);//根节点入队
- while (!queue.isEmpty()){
- //用队列里面的节点个数来控制二维数组中每个元素的大小
- int size = queue.size();
- List<Character> list = new ArrayList<>();
- while (size != 0){
- treeNode cur = queue.poll();//出队打印,并判断是否有左右孩子,若有按照从左至右的顺序入队
- list.add(cur.val);
- size--;
- System.out.println(cur.val + " ");
- if (cur.left != null){
- queue.offer(cur.left);
- }
- if (cur.right != null){
- queue.offer(cur.right);
- }
- }
- listList.add(list);
- }
-
- return listList;
- }
1.先把根节点入队
2.队列不为空,弹出元素,每次都用cur 记录,入队cur的左右孩子(可以为空,为空则入队null)
3.当遇cur遇到null时则停下判断队列里是否全为null,若是,则该二叉树为完全二叉树,否则不是完全二叉树
- public boolean isCompletelyTree(treeNode root){
- if (root == null)return true;
- else {
- Queue<treeNode> queue = new LinkedList<>();
- queue.offer(root);
- while (!queue.isEmpty()){
- treeNode cur = queue.poll();
- if (cur != null){
- queue.offer(cur.right);
- queue.offer(cur.right);
- }
- else break;//遇到cur为空,下一步判断队列里面是否全部为空
- }
- while (!queue.isEmpty()){
- treeNode treeNode = queue.poll();
- if (treeNode != null){
- return false;
- }
- }
- }
- return true;
- }
cur从根节root点开始遍历每个节点,找到p,q,判断p,q是否在root的来两侧,若pq在root的两侧,则root即为最近公共祖先,若cur已经遍历了root的左侧都没有找到p或者q,那么说明pq在root的右侧,此时移动root至root的右侧(root = root.right),再执行cur = root,cur继续从新的root遍历,寻找p或者q,判断是否在root的两侧,若是,则root即为最近公共祖先,若先找到p或者q,则先找到的节点即为最近公共祖先
总的来说就是递归判断pd是否在当前节点的两侧,若是则当前节点即为所求,若不是则先遇节点即为所求
- public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){
- if (root == null || root == p ||root == q){
- return root;
- }
- TreeNode left = lowestCommonAncestor(root.left,p,q)
- TreeNode right = lowestCommonAncestor(root.right,p,q)
- if (left != null && right != null) {//p q 分布在两侧
- return root;
- } else if (left != null) {//p q 分布在一侧,先找到哪个,哪个就为最近祖先
- return left;
- } else {
- return right;
- }
- }
方法二,利用两个栈来分别存放从根节点到 p,q 节点的路径节点,节点个数可能不一样,较长栈 减去两栈长度差值直到两栈长度相同,再同时出栈,直到拿到val相同的节点,该节点即为最近祖先
关于如何确定指定节点p的路径?
1.cur 从根节点开始遍历,左右孩子不为空就入栈
2.同时判断该节点是否为p节点
3.当穷尽一条路时仍然没有找到p节点,并且此时cur所指向的节点是没有左右孩子的,就说明但前路径不是所求路径
4.出栈,继续递归遍历,直到找到p节点,栈里所存放的节点即为寻找p节点的路径
- public boolean getPath(TreeNode node , TreeNode root, Stack<TreeNode> stack){
- if (root == null){
- return false;
- }
- stack.push(root);
- if (root == node){
- return true;
- }
- boolean flgLeft = getPath(node,root.left,stack);
- if (flgLeft == true){
- return true;
- }
- boolean flgRight = getPath(node,root.right,stack);
- if (flgRight == true){
- return true;
- }
- stack.pop();
- return false;
- }
按照以上方法求出路径,接下来就可以利用栈来求最近公共祖先
- public TreeNode lowestCommonAncestor2(TreeNode root,TreeNode p,TreeNode q){
- if (root == null){
- return null;
- }
- Stack<TreeNode> stack1 = new Stack<>();
- Stack<TreeNode> stack2 = new Stack<>();
- getPath(p,root,stack1);
- getPath(q,root,stack2);
- while (stack1.size() > stack2.size()){
- stack1.pop();
- }
- while (stack2.size() > stack1.size()){
- stack2.pop();
- }
- while (!stack2.isEmpty() && !stack1.isEmpty()){
- if (stack2.peek().equals(stack1.peek())){
- return stack2.pop();
- }else {
- stack2.pop();
- stack1.pop();
- }
- }
- return null;
- }
1.先遍历先序遍历的字符串,用cur指向
2.在 中序遍历 的指定区间内 找到cur所指向 的 相应节点,递归创建左数和右数
- class Solution1{//已知后序遍历和中序遍历创建一颗二叉树
- //postorder 给出的后序遍历序列
- //inorder 给出的中序遍历序列
-
- public int postIndex; //记录后序遍历序列的下标
- public TreeNode buildTree(int[] postorder,int[] inorder){
- int inBegin = 0;//inBegin 中序序列中 查找节点时 的 起始查找下标,初始值为0
- int inEnd = postorder.length - 1;//inEnd中序序列中 查找节点时 的 结束查找下标,初始值为length - 1
- postIndex = postorder.length -1;
- TreeNode root = buildTreeChild(postorder,inorder,inBegin,inEnd);
- return root;
- }
- private TreeNode buildTreeChild(int[] postorder,int[] inorder,int inBgin,int inEnd){
- if (inEnd >inBgin){
- return null;
- }
- TreeNode root = new TreeNode((char) postorder[postIndex]);//1.创建根节点
- //2.找到 postorder中 下标为postIndex 的节点 在inorder序列中 的下标,用 rootIndex 记录
- int rootIndex = FindRootIndex(inorder,inBgin,inEnd,postorder[postIndex]);
- postIndex--;
- //3.分别创建右子树和左子树
- root.right = buildTreeChild(postorder,inorder,rootIndex + 1,inEnd);
- root.left = buildTreeChild(postorder,inorder,inBgin,rootIndex - 1);
- return root;
- }
- private int FindRootIndex(int[] inorder,int inBgin,int inEnd,int key){//用于步骤2中寻找下标
- //inorder 中序遍历序列,被查找序列
- //inBgin 起始位置
- //inEnd 结束位置
- //查找对象的下标
- int i = inBgin;
- while (i <= inEnd){
- if (inorder[i] == key){
- return i;
- }
- i++;
- }
- return -1;
- }
-
- }
- }
思路和 已知 先中序列创建二叉树 一样,唯一不同的就是后序遍历序列中,根节点在数组的最后,因此 要从后序遍历序列的 最后一个元素开始 向前遍历数组寻找根节点
- class Solution{//已知先序遍历和中序遍历创建一颗二叉树
- //preorder 给出的先序遍历序列
- //inorder 给出的中序遍历序列
- public int preIndex = 0; //记录先序遍历序列的下标
- public TreeNode buildTree(int[] preorder,int[] inorder){
- int inBegin = 0;//中序序列中 查找节点时 的 起始查找下标,初始值为0
- int inEnd = inorder.length - 1;//中序序列中 查找节点时 的 结束查找下标,初始值为length - 1
- TreeNode root = buildTreeChild(preorder,inorder,inBegin,inEnd);
- return root;
- }
- private TreeNode buildTreeChild(int[] preorder,int[] inorder,int inBgin,int inEnd){
- if (inEnd >inBgin){
- return null;
- }
- TreeNode root = new TreeNode((char) preorder[preIndex]);//1.创建根节点
- //2.找到 preorder中 下标为preIndex 的节点 在inorder序列中 的下标,用 rootIndex 记录
- int rootIndex = FindRootIndex(inorder,inBgin,inEnd,preorder[preIndex]);
- preIndex++;
- //3.分别创建左子树和右子树
- root.left = buildTreeChild(preorder,inorder,inBgin,rootIndex - 1);
- root.right = buildTreeChild(preorder,inorder,rootIndex + 1,inEnd);
- return root;
- }
- private int FindRootIndex(int[] inorder,int inBgin,int inEnd,int key){//用于步骤2中寻找下标
- //inorder 中序遍历序列,被查找序列
- //inBgin 起始位置
- //inEnd 结束位置
- //查找对象的下标
- int i = inBgin;
- while (i <= inEnd){
- if (inorder[i] == key){
- return i;
- }
- i++;
- }
- return -1;//若没有找到,就返回-1
- }
- }
给你二叉树的根节点root,采用先序遍历,转化为一个由括号和整数组成的字符串,返回构造出的字符串
- class solution2{
- public String tree2str(TreeNode root){
- StringBuilder sbu = new StringBuilder();
- TreetoStr( root,sbu);
- return sbu.toString();
- }
- private void TreetoStr(TreeNode root,StringBuilder sbu ){
- if (root == null){
- return;
- }
- sbu.append('(');
- //1.先递归左树
- if (root.left != null){
- sbu.append('(');
- TreetoStr(root.left,sbu);
- sbu.append(')');
- }else {
- if (root.right == null){
- return;
- }
- else {
- sbu.append('(');
- sbu.append(')');
- }
-
- }
- //
- if (root.right != null){
- sbu.append('(');
- TreetoStr(root.right,sbu);
- sbu.append(')');
- }else {
- return;
- }
- }
- }
- class preOrder{
- public List<Integer> preorderTraversal(TreeNode root){
- List<Integer> list = new ArrayList<>();
- if (root == null){
- return list;
- }
- Stack<TreeNode> stack = new Stack();
- TreeNode cur = root;
- while (cur != null || !stack.isEmpty()){
- while (cur != null){//从整棵树的最左节点边开始遍历,不为空则入栈
- stack.push(cur);
- list.add((int) cur.val);
- cur = cur.left;
- }
- TreeNode top = stack.pop();
- cur = top.right;
- }
- return list;
- }
- }
- class inOrder{
- public List<Integer> inorderTraverasal(TreeNode root){
- List<Integer> list = new LinkedList<>();
- Stack<TreeNode> stack = new Stack<>();
- TreeNode cur = root;
- if (root == null){
- return list;
- }
- while (!stack.isEmpty() || cur != null){
- while (cur!=null){
- stack.push(cur);
- cur=cur.left;
-
- }
- TreeNode top = stack.pop();
- list.add((int) cur.val);
- cur = top.right;
- }
- return list;
- }
- }
- class postOrder{
- public List<Integer> inorderTraverasal(TreeNode root){
- List<Integer> list = new LinkedList<>();
- Stack<TreeNode> stack = new Stack<>();
- TreeNode cur = root;
- TreeNode prev = null;
- if (root == null){
- return list;
- }
- while (!stack.isEmpty() || cur != null){
- while (cur!=null){
- stack.push(cur);
- cur=cur.left;
- }
- TreeNode top = stack.peek();
- if (top.right==null || top.right == prev){
- stack.pop();
- list.add((int) top.val);
- prev = top;
- }else {
- cur = cur.right;
- }
- }
- return list;
- }
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。