102. 二叉树的层序遍历
题目链接:https://leetcode.cn/problems/binary-tree-level-order-traversal/
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[][]}
*/
//思路:bfs,用队列
var levelOrder = function(root) {
if(root == null){
return []
}
let queue = []
let res = []
queue.push(root)
let num = 1
let nextNum = 0
while(num>0){
let tmp = []
for(let i =0;i<num;i++){
let node = queue.shift()
tmp.push(node.val)
if(node.left){
queue.push(node.left)
nextNum++
}
if(node.right){
queue.push(node.right)
nextNum++
}
}
res.push(tmp)
num = nextNum
nextNum=0
}
return res
};
看了题解后发现可以简化,可以直接用num = queue.length就行了
卡哥说刷完这道可以刷十道
我先跳过了
226.翻转二叉树
题目链接:https://leetcode.cn/problems/invert-binary-tree/
递归是显然的
/**
* 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 tmp = root.left
root.left = root.right
root.right = tmp
if(root.left){
invertTree(root.left)
}
if(root.right){
invertTree(root.right)
}
return root
};
非递归:层序遍历,更直观;毕竟涉及到左右交换,dfs的顺序感觉容易乱
/**
* 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 queue = []
let num = 1
queue.push(root)
while(num>0){
for(let i =0 ; i<num;i++){
let node = queue.shift()
let tmp = node.left
node.left = node.right
node.right = tmp
if(node.left){
queue.push(node.left)
}
if(node.right){
queue.push(node.right)
}
}
num = queue.length
}
return root
};
不过后面发现:事实上是无所谓的,只要反转过后再压栈就没问题
101. 对称二叉树
最后还是用了层序遍历,递归的方法我反而想不出(而且效率好低)
/**
* 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 {boolean}
*/
//思路1:中序遍历投影后,检查数组是否对称
//思路2:层序遍历后检查每层是否对称
//递归么...感觉子问题好像不好分割啊
//思路有问题:null这种会导致不对称的值被忽略了
//如果要记录null,那我的原来的迭代思路就废了...尬住
var isSymmetric = function(root) {
let queue = []
let num = 1
queue.push(root)
while(num>0){
let tmp = []
for(let i =0; i<num;i++){
let node = queue.shift()
tmp.push(node.left?node.left.val:null)
tmp.push(node.right?node.right.val:null)
if(node.left){
queue.push(node.left)
}
if(node.right){
queue.push(node.right)
}
}
// console.log(tmp)
if(!judge(tmp)){
return false
}
num = queue.length
}
return true
};
function judge(arr){
let l = 0, r = arr.length-1
while(l<r){
if(arr[l]!=arr[r]){
return false
}
l++
r--
}
return true
}
看了卡哥的题解以后发现递归法是很值得学习的
尤其是写递归的思路
1.确定递归函数的参数和返回值
2.确定递归终止条件/基线条件
3.确定单层递归逻辑
/**
* 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 {boolean}
*/
//参考思路:递归
//参数:左树根节点,右数根节点;
//终止条件:比较结果为false;或传入的节点为空;
//单层逻辑:比较左树和右树是否是轴对称的;也就是比较两个结点是否相等,然后比较左的右子树和右的左子树&&(略)
var isSymmetric = function(root) {
return compareTree(root.left,root.right)
};
function compareTree(left,right){
if(left==null&&right==null){
return true
}else if(left==null&&right!=null||left!=null&&right==null){
return false
}else{
if(left.val!=right.val){
return false
}else{
return compareTree(left.right,right.left)&&compareTree(left.left,right.right)
}
}
}