《关于二叉树一些数据结构和算法相关的题目.doc》由会员分享,可在线阅读,更多相关《关于二叉树一些数据结构和算法相关的题目.doc(4页珍藏版)》请在三一文库上搜索。
1、关于二叉树一些数据结构和算法相关的题目最近总结了一些数据结构和算法相关的题目,这是第一篇文章,关于二叉树的。先上二叉树的数据结构:class TreeNode int val; /左孩子 TreeNode left; /右孩子 TreeNode right;二叉树的题目普遍可以用递归和迭代的方式来解1. 求二叉树的最大深度int maxDeath(TreeNode node) if(node=null) return 0; int left = maxDeath(node.left); int right = maxDeath(node.right); return Math.max(left
2、,right) + 1;2. 求二叉树的最小深度int getMinDepth(TreeNode root) if(root = null) return 0; return getMin(root); int getMin(TreeNode root) if(root = null) return Integer.MAX_VALUE; if(root.left = null return Math.min(getMin(root.left),getMin(root.right) + 1; 3. 求二叉树中节点的个数int numOfTreeNode(TreeNode root) if(roo
3、t = null) return 0; int left = numOfTreeNode(root.left); int right = numOfTreeNode(root.right); return left + right + 1; 4. 求二叉树中叶子节点的个数int numsOfNoChildNode(TreeNode root) if(root = null) return 0; if(root.left=null return numsOfNodeTreeNode(root.left)+numsOfNodeTreeNode(root.right); 5. 求二叉树中第k层节点的
4、个数int numsOfkLevelTreeNode(TreeNode root,int k) if(root = null|k1) return -1; return Math.max(left, right) + 1; 7.判断二叉树是否是完全二叉树什么是完全二叉树呢?参见boolean isCompleteTreeNode(TreeNode root) if(root = null) return false; Queue queue = new LinkedList(); queue.add(root); boolean result = true; boolean hasNoChil
5、d = false; while(!queue.isEmpty() TreeNode current = queue.remove(); if(hasNoChild) if(current.left!=null|current.right!=null) result = false; break; else if(current.left!=null queue.add(current.right); else if(current.left!=null hasNoChild = true; else if(current.left=null break; else hasNoChild =
6、true; return result; 8. 两个二叉树是否完全相同boolean isSameTreeNode(TreeNode t1,TreeNode t2) if(t1=null else if(t1=null|t2=null) return false; if(t1.val != t2.val) return false; boolean left = isSameTreeNode(t1.left,t2.left); boolean right = isSameTreeNode(t1.right,t2.right); return left 9. 两个二叉树是否互为镜像boolean
7、 isMirror(TreeNode t1,TreeNode t2) if(t1=null if(t1=null|t2=null) return false; if(t1.val != t2.val) return false; return isMirror(t1.left,t2.right) 10. 翻转二叉树or镜像二叉树TreeNode mirrorTreeNode(TreeNode root) if(root = null) return null; TreeNode left = mirrorTreeNode(root.left); TreeNode right = mirrorT
8、reeNode(root.right); root.left = right; root.right = left; return root; 11. 求两个二叉树的最低公共祖先节点TreeNode getLastCommonParent(TreeNode root,TreeNode t1,TreeNode t2) if(findNode(root.left,t1) if(findNode(root.right,t2) return root; else return getLastCommonParent(root.left,t1,t2); else if(findNode(root.lef
9、t,t2) return root; else return getLastCommonParent(root.right,t1,t2) / 查找节点node是否在当前 二叉树中 boolean findNode(TreeNode root,TreeNode node) if(root = null | node = null) return false; if(root = node) return true; boolean found = findNode(root.left,node); if(!found) found = findNode(root.right,node); ret
10、urn found; 12. 二叉树的前序遍历迭代解法ArrayList preOrder(TreeNode root) Stack stack = new Stack(); ArrayList list = new ArrayList(); if(root = null) return list; stack.push(root); while(!stack.empty() TreeNode node = stack.pop(); list.add(node.val); if(node.right!=null) stack.push(node.right); if(node.left !=
11、null) stack.push(node.left); return list; 递归解法ArrayList preOrderReverse(TreeNode root) ArrayList result = new ArrayList(); preOrder2(root,result); return result; void preOrder2(TreeNode root,ArrayList result) if(root = null) return; result.add(root.val); preOrder2(root.left,result); preOrder2(root.r
12、ight,result); 13. 二叉树的中序遍历ArrayList inOrder(TreeNode root) ArrayList list = new ArrayList(); Stack stack = new Stack(); TreeNode current = root; while(current != null| !stack.empty() while(current != null) stack.add(current); current = current.left; current = stack.peek(); stack.pop(); list.add(curr
13、ent.val); current = current.right; return list; 14.二叉树的后序遍历ArrayList postOrder(TreeNode root) ArrayList list = new ArrayList(); if(root = null) return list; list.addAll(postOrder(root.left); list.addAll(postOrder(root.right); list.add(root.val); return list; 15.前序遍历和后序遍历构造二叉树TreeNode buildTreeNode(i
14、nt preorder,int inorder) if(preorder.length!=inorder.length) return null; return myBuildTree(inorder,0,inorder.length-1,preorder,0,preorder.length-1); TreeNode myBuildTree(int inorder,int instart,int inend,int preorder,int prestart,int preend) if(instartinend) return null; TreeNode root = new TreeNo
15、de(preorderprestart); int position = findPosition(inorder,instart,inend,preorderstart); root.left = myBuildTree(inorder,instart,position-1,preorder,prestart+1,prestart+position-instart); root.right = myBuildTree(inorder,position+1,inend,preorder,position-inend+preend+1,preend); return root; int find
16、Position(int arr,int start,int end,int key) int i; for(i = start;inode.val) tmp = tmp.left; else tmp = tmp.right; if(last!=null) if(last.valnode.val) last.left = node; else last.right = node; return root; 17.输入一个二叉树和一个整数,打印出二叉树中节点值的和等于输入整数所有的路径void findPath(TreeNode r,int i) if(root = null) return;
17、Stack stack = new Stack(); int currentSum = 0; findPath(r, i, stack, currentSum); void findPath(TreeNode r,int i,Stack stack,int currentSum) currentSum+=r.val; stack.push(r.val); if(r.left=null if(r.left!=null) findPath(r.left, i, stack, currentSum); if(r.right!=null) findPath(r.right, i, stack, cur
18、rentSum); stack.pop(); 18.二叉树的搜索区间给定两个值 k1 和 k2(k1 result; ArrayList searchRange(TreeNode root,int k1,int k2) result = new ArrayList(); searchHelper(root,k1,k2); return result; void searchHelper(TreeNode root,int k1,int k2) if(root = null) return; if(root.valk1) searchHelper(root.left,k1,k2); if(roo
19、t.val=k1 if(root.val levelOrder(TreeNode root) ArrayList result = new ArrayList(); if(root = null) return result; Queue queue = new LinkedList(); queue.offer(root); while(!queue.isEmpty() int size = queue.size(); ArrayList level = new ArrayList(): for(int i = 0;i teger.MAX_VALUE; public boolean firstNode = true; public boolean isValidBST(TreeNode root) / write your code here if(root=null) return true; if(!isValidBST(root.left) return false; if(!firstNode firstNode = false; lastVal = root.val; if (!isValidBST(root.right) return false; return true; 深刻的理解这些题的解法思路,在面试中的二叉树题目就应该没有什么问题
链接地址:https://www.31doc.com/p-3387942.html