牛客算法--第七章

xiaoxiao2021-02-28  7

牛客算法–第七章

题目一 分别用递归和非递归方式实现二叉树先序、中序和后序遍历 【题目】 用递归和非递归方式,分别按照二叉树先序、中序和后序打印所有的节点。我们约定:先序遍历顺序为根、左、右;中序遍历顺序为左、根、右;后序遍历顺序为左、右、根。

前序遍历为“根左右”:

递归C++版本:

void preorder(node* root) { if(root==NULL) { return; //到达空树,递归边界 } //访问根结点root,例如将其数据域输出 printf("%d\n",root->value); //访问左子树 preorder(root->lchild); //访问右子树 preorder(root->rchild); }

非递归JAVA版本:

public static void preOrderUnRecur(Node head){ System.out.print("preorder: "); if(head != null) { Stack<Node> stack = new Stack<Node>(); stack.add(head); while(!stack.isEmpty()){ head = stack.pop(); Systemp.out.print(head.value + " "); if(head.right != null) { stack.push(head.right); } if(head.left != null) { stack.push(head.left) } } } System.out.println(); }

非递归版本核心思想就是用栈。 因为先序遍历的要求是“根左右”,而栈的结构是完成数据先进后出的。所以我们应该先判断一个结点右子树是否为空,如果不为空,就将其压入栈中;然后再判断一个结点左子树是否为空,如果不为空,就将其压入栈中。这样就保证了一个结点的左子树先于右子树弹出栈。我们遍历的过程就是弹出栈的过程,我们总是弹出栈顶最高的结点,如果该结点有左右子结点,就将其子结点按“先右后左”的顺序压入栈中;如果没有的话,也就是叶子结点,因为有if语句的判断作用,它没有子结点会在这一回合压入,并且会将其自身从栈中弹出。

中序遍历为“左根右”:

递归C++版本:

void inorder(node* root) { if(root == NULL) { return; } inorder(root->lchild); printf("%d\n",root->value); inorder(root->rchild); }

非递归JAVA版本:

public static void inOrderUnRecur(Node head){ System.out.print("inorder: "); if(head != null) { Stack<Node> stack = new Stack<Node>(); while(!stack.isEmpty() || head != null ){ if(head != null){ stack.push(head); head = head.left; }else{ head = stack.pop(); System.out.print(head.value + " " ); head = head.right; } } } System.out.println(); }

非递归中序遍历的顺序因为是“左根右”,我们实际上把一颗树想成下面:

/ / / / / / / / /

就是想成一排排左斜线的样子。 就是有一丝丝“左倾”的分子都要让他入栈。啥意思呢?就是第一优先级是“左左”,第二优先级是“右左”。

后序遍历为“左右根”:

递归C++版本:

void postorder(node* root) { if(root == NULL) { return; } postorder(root->lchild); postorder(root->rchild); printf("%d\n",root->value); }

非递归JAVA版本:

非递归后序遍历的核心思想是用两个栈stack1和stack2.后序遍历要求的是“左右根”,我们看一下它的逆序,就是“根右左”,那么,如何做呢?就是前面非递归先序遍历中,栈中先压右后压左,最终实现了“根左右”,现在我们栈中先压左后压右,自然就可以得到“根右左”了。接下来第二个stack2的作用实际上就是起一个逆序的作用,最终就可以得到“左右根”的效果了。当然,实现逆序,也不一定用栈,我们可以存储在容器中,然后进行reverse就可以了。

提前预告,下面的题目二和题目三都是套路题,要掌握。

题目二 找到二叉树中的最大搜索二叉子树 【题目】 给定一棵二叉树的头节点 head,已知其中所有节点的值都不一样,找到含有节点最多的搜索二叉子 树,并返回这棵子树的头节点。 【要求】 如果节点数为 N,要求时间复杂度为 O(N),额外空间复杂度为 O(h),h 为二叉树的高度。

首先,要弄明白最大子树和最大拓扑结构的**区别。**一个点包括左右子树都满足条件,这个点为根结点的树才算是一颗符合条件的子树。

假如我们有一个函数F(…)可以返回以下4个信息:

1.最大搜索子树头结点 2.整棵树的min值 3.整棵树的max值 4.整棵树符合条件的size public static Node biggestSubBST(Node head){ //0->size,1->min,2->max int[] record = new int[3]; return posOrder(head,record); } public static Node posOrder(Node head,int[] record){ if(head == null) { record[0] = 0; record[1] = Integer.MAX_VALUE; record[2] = Integer.MIN_VALUE; return null; } int value = head.value; Node left = head.left; Node right = head.right; Node lBST = postOrder(left,record); int lSize = record[0]; int lMin = record[1]; int lMax = record[2]; Node rBST = posOrder(right,record); int rSize = record[0]; int rMin = record[1]; int rMax = record[2]; record[1] = Math.min(lMin,value); record[2] = Math.max(rMax,value); if( left == lBST && right == rBST && lMax < value && value < rMin ) { record[0] = lSize + rSize +1; return head; } record[0] = Math.max(lSize,rSize); return lSize > rSize ? lBST : rBST; } 题目三 二叉树节点间的最大距离问题 【题目】 从二叉树的节点 A 出发,可以向上或者向下走,但沿途的节点只能经过一次,当到达节点 B 时,路 径上的节点数叫作 A 到 B 的距离。求整棵树上节点间的最大距离。 【要求】 如果二叉树的节点数为 N,时间复杂度要求为 O(N)。 public static int maxDistance(Node head)}{ int[] record = new int[1]; return posOrder(head,record); } public static int posOrder(Node head,int[] record){ if(head == null){ record[0] =0; return 0; } int lMax = posOrder(head.left,record); int maxFromLeft = record[0]; int rMax = posOrder(head.right,record); int maxFromRight = record[0]; int curNodeMax = maxFromLeft + maxFromRight+1; record[0] = Math.max(maxFromLeft, maxFromRight )+1; return Math.max(Math.max(lMax,rMax),curNodeMax); } 题目五 在二叉树中找到累加和为指定值的最长路径长度 【题目】 给定一棵二叉树的头节点 head 和一个 32 位整数 sum,二叉树节点值类型为整型,求累加和为 sum 的最长路径长度。路径是指从某个节点往下,每次最多选择一个孩子节点或者不选所形成的节点链。 ,额外空间复杂度为 O(h),h 为二叉树的高度。

总结,解决本题需要先复习以下原来的一个算法原型,求一个数组中指定和为k的最长子数组。

怎么求解呢?用到哈希map。

首先在map中插入(0,-1)键值对,因为数组下标是从0开始的,所以提前设置从-1位置开始的值是0。 遍历一遍数组,在遍历的过程中进行累加,累加值是key,如果这个key值在map中没有出现过,就将其加入map中,对应的value值是遍历到的下标,如果已经出现过了,就不进行理会。

算法的原理就是假设从0到i的累加和为num1,我们要求以i结尾的累加和为指定k的最长子数组和,就是从map中找到num1-k对应的key值,找出对应的index,符合条件的最长子数组就是index~i的数组。我们如何求长度呢?i-index+1。 同样我们在遍历的过程中可以得出所有以0~n结尾的累加和为指定k的最长子数组和,所以我们在其中选出一个最大值就可以了。

回归本题,树的操作,和之前的又有一些不同,需要注意数据的保存,在递归的过程中自然实现保存。

代码中的sum就是指定和k,数组中的index,就是对应树中的level:

public static int getMaxLength(Node head,int sum){ HashMap<Integer,Integer> sumMap = new HashMap<Integer,Integer>(); sumMap.put(0,0);//important return preOrder(head,sum,0,1,0,sumMap); } public static int preOrder(Node head,int sum,int preSum, int level ,int maxLen,HashMap<Integer,Integer> sumMap ){ if(head == null) { return maxLen; } int curSum = preSum + head.value; if(!sumMap.containsKey(curSum)){ sumMap.put(curSum,level); } if(sumMap.containsKey(curSum - sum)){ maxLen = Math.max(level - sumMap.get(curSum - k),maxLen); } maxLen = preOrder(head.left,sum,curSum,level+1,maxLen,sumMap); maxLen = preOrder(head.right,sum,curSum,level+1,maxLen,sumMap); if(level == sumMap.get(curSum)){ sumMap.remove(curSum); } return maxLen; }
转载请注明原文地址: https://www.6miu.com/read-1950360.html

最新回复(0)