华为OD算法复习6——二叉树 Javascript
·
这些力扣题目来源：AI推荐+
karshey博主
目录
144 前序遍历（通过）
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function(root) {
if (root==null) return [];
let cur = root.val;
let left = preorderTraversal(root.left);
let right = preorderTraversal(root.right);
return [cur,...left,...right]
};94 中序遍历（通过）
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function(root) {
if(root==null) return [];
let cur = root.val;
let left = inorderTraversal(root.left);
let right = inorderTraversal(root.right);
return [...left,cur,...right];
};145. 二叉树的后序遍历（通过）
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var postorderTraversal = function(root) {
if(root==null) return [];
let cur=root.val;
let left=postorderTraversal(root.left);
let right=postorderTraversal(root.right);
return [...left,...right,cur];
};102.二叉树的层序遍历（通过）
注意空节点的可能，返回空数组
层序遍历是队列，先进先出。所以使用shift而不是pop
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
let node9 = new TreeNode(9,null,null);
let node15 = new TreeNode(15,null,null);
let node7 = new TreeNode(7,null,null);
let node20 = new TreeNode(20,node15,node7);
let node3 = new TreeNode(3,node9,node20);
let root = node3;
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
let ans=[];
let thisLevel = [];
if(root!=null)thisLevel.push(root); //pay attention to the empty node
while(thisLevel.length!=0){
let nextLevel=[];
let level_ans =[]
while(thisLevel.length!=0){
let node = thisLevel.shift(); //first in first out
level_ans.push(node.val);
if(node.left!=null){ nextLevel.push(node.left); }
if(node.right!=null){nextLevel.push(node.right);}
}
thisLevel=nextLevel;
nextLevel=[];
ans.push(level_ans);
}
return ans;
};
console.log(levelOrder(root));105 前序 + 中序构造二叉树（通过）
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
/**
* @param {number[]} preorder
* @param {number[]} inorder
* @return {TreeNode}
*/
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
// preorder = [3,9], inorder = [9,3]
var buildTree = function(preorder, inorder) {
if(preorder.length==0) return null;
let pre_root_arr = preorder[0];
let in_left_arr = inorder.slice(0,inorder.indexOf(preorder[0]));
let in_right_arr = inorder.slice(inorder.indexOf(preorder[0])+1);
let pre_left_arr = preorder.slice(1,1+in_left_arr.length);
let pre_right_arr = preorder.slice(1+in_left_arr.length);
let left_node = buildTree(pre_left_arr, in_left_arr);
let right_node = buildTree(pre_right_arr, in_right_arr);
let cur_node = new TreeNode(pre_root_arr, left_node, right_node);
return cur_node;
};
console.log(buildTree(preorder,inorder));106 中序 + 后序构造二叉树（通过）
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
/**
* @param {number[]} inorder
* @param {number[]} postorder
* @return {TreeNode}
*/
inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
var buildTree = function(inorder, postorder) {
if(postorder.length==0) return null;
let cur_val = postorder[postorder.length-1];
let inorder_left_arr = inorder.slice(0,inorder.indexOf(cur_val));
let inorder_right_arr = inorder.slice(inorder.indexOf(cur_val)+1);
let postorder_left_arr = postorder.slice(0,inorder_left_arr.length);
let postorder_right_arr = postorder.slice(inorder_left_arr.length, inorder_left_arr.length+inorder_right_arr.length);
let left_node = buildTree(inorder_left_arr,postorder_left_arr);
let right_node = buildTree(inorder_right_arr,postorder_right_arr);
let cur_node = new TreeNode(cur_val,left_node, right_node);
return cur_node;
};
console.log(buildTree(inorder,postorder));104 最大深度（DFS/BFS）（通过）
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function(root) {
if (root==null) return 0;
return Math.max(1+maxDepth(root.left),1+maxDepth(root.right));
};111 最小深度（BFS 更优，OD 常考）（通过）
利用层序遍历，只要发现左右孩子都为null就返回目前的层数
如果每一层的所有节点都至少有一个孩子，那么目前的层数+1，进入下一轮循环
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var minDepth = function(root) {
if (root == null) return 0;
let thisLevel = [];
thisLevel.push(root);
let ans = 1;
while(thisLevel.length != 0){
let nextLevel = [];
while(thisLevel.length!=0){
let temp = thisLevel.shift();
let left = temp.left;
let right = temp.right;
if(left==null && right==null) return ans;
if(left) nextLevel.push(left);
if(right) nextLevel.push(right);
}
thisLevel = nextLevel;
nextLevel = [];
ans+=1;
}
return ans;
};226 翻转二叉树（递归模板，OD 简单变种）（通过）
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var invertTree = function(root) {
if (root==null) return root;
let left = root.left;
let right = root.right;
left = invertTree(left);
right =invertTree(right);
root.left = right;
root.right = left;
return root;
};236 二叉树最近公共祖先（OD 中等题高频）（通过）
我们根据左右孩子是否包含p或q分为三种情况：
1. 左孩子和有孩子都包含p或q，证明当前父节点就是目标节点 if (left && right ) return root;
2. 只有左孩子包含p或q，或者只有有孩子包含p或q，证明 目标节点在左右孩子之一里面，使用递归查找 let left = lowestCommonAncestor(root.left,p,q); 到时候返回找到的左右孩子的子节点即可
3. 左右孩子都不包含p或q，证明 父节点一定包含p或q。if(root.val == p.val || root.val == q.val) return root;
4. 找不到的时候就返回 null 节点
function TreeNode(val, node_left, node_right) {
this.val = val;
this.left = node_left;
this.right = node_right;
}
let node6 = new TreeNode(6, null, null)
let node7 = new TreeNode(7, null, null)
let node4 = new TreeNode(4, null, null)
let node0 = new TreeNode(0, null, null)
let node8 = new TreeNode(8, null, null)
let node2 = new TreeNode(2, node7, node4);
let node1 = new TreeNode(1, node0, node8);
let node5 = new TreeNode(5, node6, node2);
let node3 = new TreeNode(3, node5, node1);
let root = node3;
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function (root, p, q) {
if (root==null) return null;
if(root.val == p.val || root.val == q.val) return root;
let left = lowestCommonAncestor(root.left,p,q);
let right =lowestCommonAncestor(root.right,p,q);
if (left && right ) return root;
return left || right;
//通过30/32个用例 超时 因为使用了重复递归
// let existInChild = function (target, node) {
// if (node == null) return false;
// if (target.val == node.val) return true;
// let left = existInChild(target, node.left);
// let right = existInChild(target, node.right);
// return left || right;
// }
// if(root.val == p.val || root.val == q.val) return root;
// let p_left_exist = existInChild(p, root.left);
// let p_right_exist = existInChild(p, root.right);
// let q_left_exist = existInChild(q, root.left);
// let q_right_exist = existInChild(q, root.right);
// if (p_left_exist && q_right_exist) return root;
// if (q_left_exist && p_right_exist) return root;
// if (p_left_exist && q_left_exist) {
// return lowestCommonAncestor(root.left, p, q);
// }
// if (p_right_exist && q_right_exist){
// return lowestCommonAncestor(root.right, p, q)
// }
};
console.log(lowestCommonAncestor(root, node0,node8));
112 路径总和（DFS 路径题模板）（通过）
把问题简化
1. 特殊边界值：空树//null节点直接返回false
2. 如果是叶子节点，判断当前值是否等于targetSum
3. 看左右节点是否分别相等于targetSum减去当前节点的值。只要左右节点有一个能找到代表整个二叉树可以找到
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} targetSum
* @return {boolean}
*/
var hasPathSum = function(root, targetSum) {
if(root==null) return false;
if(root.left==null && root.right==null) {
if(targetSum==root.val) return true;
else return false;
}
let left = hasPathSum(root.left, targetSum-root.val);
let right = hasPathSum(root.right, targetSum-root.val);
return left || right;
};199 二叉树右视图（层序遍历变种，OD 常考）（通过）
在大循环外面设置一个临时变量last记录每一层的最后一个元素
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var rightSideView = function(root) {
if (root==null) return [];
let ans=[];
let thisLevel = [];
thisLevel.push(root);
let last=root;
while(thisLevel.length!=0){
let nextLevel = [];
ans.push(last.val);
while(thisLevel.length!=0){
let temp = thisLevel.shift();
let left = temp.left;
let right = temp.right;
if(left) {
nextLevel.push(left);
last=left;
}
if(right){
nextLevel.push(right);
last=right;
}
}
thisLevel=nextLevel;
nextLevel=[];
}
return ans;
};
AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。
更多推荐
12
0- 0
已为社区贡献3条内容
所有评论(0)