| 前端二叉树面试题 | 您所在的位置：网站首页 › 二叉树的面试题 › 前端二叉树面试题 |
前端二叉树面试题
|
文章目录
二叉树常见题型二叉树的中序遍历前序遍历后序遍历重建二叉树对称的二叉树二叉树的镜像二叉搜索树中第k小的元素二叉搜索树的后序遍历序列二叉树的最大深度二叉树的最小深度平衡二叉树二叉树中和为某一值的路径二叉搜索树与双向链表树的子结构
二叉树
二叉树是树结构中一种典型的树状结构，每个节点最多只能有两个子节点，一个是左侧子节点，一个是右侧子节点。 二叉树中又有一种比较典型的结构，称为二叉搜索树(BST)，它允许左侧节点存储的值比父节点小，右侧存储的值比父节点大(或相等)。 常见题型 二叉树的中序遍历给定一个二叉树，返回它的中序遍历 //递归实现 var inorderTraversal = function(root, array=[]){ if(root){ inorderTraversal(root.left,array); array.push(root.val); inorderTraversal(root.right,array); } return array; };给定一个二叉树，返回前序遍历 //递归实现 var preorderTraversal = function(root, array=[]){ if(root){ array.push(root.val); inorderTraversal(root.left); inorderTraversal(root.right); } return array; }; //非递归实现 var preorderTraversal = function(root){ let array = []; let stack = []; let cur = root; while(cur || stack.length > 0){ while(cur){ array.push(cur.val); stack.push(cur); cur = cur.left; } cur = stack.pop(); cur = cur.right; } return array; } 后序遍历给定一个二叉树，返回它的后序遍历 //递归实现 var postorderTraversal = function(root, array=[]){ if(root){ inorderTraversal(root.left); inorderTraversal(root.right); array.push(root.val); } return array; }; //非递归实现 //1.从根节点开始遍历，找左侧子节点并压入栈中 //2.从栈底元素(即根节点)开始找到右侧子节点，若栈顶节点的右节点为空或右节点被访问过，则节点出栈，并访问它，并将节点标记为已访问 //3.若栈顶节点 var postorderTraversal = function(root){ let arr = []; let stack = []; let last = null; //标记上一个访问的节点 let cur = root; while(cur || stack.length > 0){ while(cur){ stack.push(cur); cur = cur.left; } //找到根节点 cur = stack[stack.length - 1]; if(!cur.right || cur.right == last){ cur = stack.pop(); arr.push(cur.val); last = cur; cur = null; }else{ cur = cur.right; } } return arr; } 重建二叉树输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 例如输入前序遍历序列[3,9,20,15,7]和中序遍历序列[9,3,15,20,7]，则重建二叉树并返回。 根据前面的遍历情况： 前序遍历：根节点 + 左侧节点的前序遍历 + 右侧节点的前序遍历，依次递归 中序遍历：左侧节点中序遍历 + 根节点 + 右侧节点的中序遍历， 依次类推 后序遍历：左侧节点后序遍历 + 右侧节点后序遍历 + 根节点，依次类推 因此根据以上规律： 前序遍历第一个便是根节点 root找到中序遍历中根节点root的位置，根节点左侧为左子树，右侧为右子树截取左子树的中序遍历、右子树的中序遍历截取左子树的前序遍历，右子树的前序遍历根据上述规则重建二叉树请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。 如 二叉树 [1,2,2,3,4,4,3] 是对称的。 判断是否为二叉树，需要满足： 二叉树的两个根节点相等左子树的右节点和右子树的左节点相同右子树的左节点和左子树的右节点相同递归所有节点满足以上条件即为对称二叉树 /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {boolean} */ var isSymmetric = function(root) { return isSymmetricalTree(root, root) }; function isSymmetricalTree(node1,node2){ if(!node1 && !node2){ return true; } if(!node1 || !node2){ return false; } if(node1.val != node2.val){ return false; } return isSymmetricalTree(node1.left, node2.right) && isSymmetricalTree(node1.right, node2.left) } 二叉树的镜像输入一个二叉树，输出它的镜像 思路：递归交换所有节点左右节点的位置 var mirrorTree = function(root) { if(root){ [root.right, root.left] = [root.left, root.right]; mirrorTree(root.right); mirrorTree(root.left); } return root; }; 二叉搜索树中第k小的元素给定一个二叉搜索树，找出其中第k个最小的元素 说明:假设k总为 1 if(root){ middleThrough(root.left,array); array.push(root.val); middleThrough(root.right,array); } return array; } //非递归实现 var kthSmallest = function(root, k) { const array = []; const stack = []; let cur = root; while(cur || stack.length > 0){ while(cur){ stack.push(cur); cur = cur.left; } cur = stack.pop(); //只需要前k个元素即可 if(array.length break; } cur = cur.right; } reutrn array[k-1]; } 二叉搜索树的后序遍历序列 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 若输入[1,6,3,2,5]，则返回false 若输入[1,3,2,6,5]，则返回true 思路： 后序遍历分为三个部分：最后一个节点为根节点，第二部分为左子树的值都比根节点小，第三部分为右子树的值比根节点大 先检测左子树，左侧比根节点小的值都为左子树的值除最后一个节点外和左子树外的其他值为右子树，右子树中只要存在一个值比根节点小，则返回false若存在左右子树，则递归检测左右子树是否符合条件 var verifyPostorder = function(postorder) { if(postorder.length===0){return true;} //数组长度为0返回true if(postorder && postorder.length > 0){ let root = postorder[postorder.length-1]; //i的值即为区分左右子树的分界点 for(var i = 0;i break; } } //i以后除了最后一个节点即为右子树 for(var j = i;j return false; } } let left = true; if(i>0){ left = verifyPostorder(postorder.slice(0,i)); } let right = true; if(i return !root ? 0 : Math.max(maxDepth(root.left),maxDepth(root.right))+1; }; //迭代写法 //BFS写法，每一层都遍历完所有节点后，n+1，然后再去遍历下一层节点 var maxDepth = function(root){ if(!root){return 0;} let quene = [root],n = 0; while(quene.length){ let arr = []; while(quene.length){ let cur = quene.shift(); if(cur.left){arr.push(cur.left);} if(cur.right){arr.push(cur.right);} } n++; quene = arr; } return n; }; 二叉树的最小深度给定一个二叉树，找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 思路： 若左右子树都不为空，则左子树最小深度和右子树最小深度的最小值+1若左子树为空，则右子树的最小深度+1若右子树为空，则左子树的最小深度+1 var minDepth = function(root) { if(!root){return 0;} if(!root.left){return 1 + minDepth(root.right);} if(!root.right){return 1 + minDepth(root.left);} return Math.min(minDepth(root.left),minDepth(root.right)) + 1; } //广度优先搜索+迭代 var minDepth = function(root){ if(!root){return 0;} let quene = [root], n = 0; while(quene.length){ n++; let len = quene.length; while(len--){ let node = quene.shift(); if(!node.left && !node.right){reutrn n;} if(node.left){quene.push(node.left);} if(node.right){quene.push(node.right);} } } }; 平衡二叉树给定一个二叉树，判断它是否是高度平衡的二叉树。 一棵高度平衡二叉树定义为：每个节点的左右两个子树的高度差的绝对值不超过1。 思路： 后序遍历二叉树在遍历二叉树每个节点前都会遍历其左右子树比较左右子树的深度，若差值大于1，则当前子树不平衡，返回false左右子树中有一个是不平衡的，则该二叉树就不平衡若左右子树平衡，返回true var isBalanced = function(root) { return balanced(root) !== -1; }; function balanced(node){ if(!node){ return 0; } let left = balanced(node.left); let right = balanced(node.right); if(left === -1 || right === -1 || Math.abs(left-right) > 1){ return -1; } return Math.max(left, right) + 1; } 二叉树中和为某一值的路径输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。 示例:给定如下二叉树，以及目标和 sum = 22， 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1返回:[[5,4,11,2],[5,8,4,5]] 思路：设定一个结果数组result来存储所有符合条件的路径；用一个栈stack来存储当前路径中的节点；设定一个target来标识当前路径值的和 从根节点开始深度优先遍历，每经过一个节点，将节点入栈到达叶子节点，且当前路径之和等于给定目标值，则将其加入结果数组遍历到二叉树的某个节点时可能有2个符合的路径，选择左子树或右子树若存在左子树，则继续向左子树递归若存在右子树，则继续向右子树递归若上述条件不符合，或已经遍历过这一条路径，将当前节点出栈，向上回溯 var pathSum = function(root, sum) { const result = []; if(root){ findPath(root,sum,[],0,result); } return result; }; function findPath(node,sum,stack,target,result){ stack.push(node.val); target += node.val; if(!node.left && !node.right && target === sum){ result.push(stack.slice(0)); } if(node.left){ findPath(node.left,sum,stack,target,result); } if(node.right){ findPath(node.right,sum,stack,target,result); } stack.pop(); } 二叉搜索树与双向链表输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。 思路：二叉搜索树的中序遍历是按照节点值大小排序的，因此需要求出中序遍历 递归左子树，找到左子树的最后一个节点，即为排序链表的头节点当前节点变为已经完成转换的链表的最后一个节点递归右子树，找到当前树的最后一个节点回溯到上一层，进行链接输入两棵二叉树A和B，判断B是不是A的子结构(约定空树不是任意一个树的子结构) 若B是A的子结构，则A中有出现和B相同的结构和节点值 思路： 首先找到A树和B树根节点相同的节点从此节点开始，递归A、B树比较是否有不同节点 var isSubStructure = function(A, B) { let result = false; if(A && B){ if(A.val === B.val){ result = compare(A,B); } if(!result){ result = isSubStructure(A.right,B); } if(!result){ result = isSubStructure(A.left,B); } } return result; }; function compare(node1,node2){ if(!node2){return true;} if(!node1){return false;} if(node1.val !== node2.val){return false;} return compare(node1.right,node2.right) && compare(node1.left,node2.left); } |
【本文地址】
公司简介
联系我们