递归 function lowestCommonAncestor( root , p , q ) { if(root==null) return null; // 如果两个值都小于根节点，说明祖先在左子树一侧 if(p<root.val && q<root.val) return lowestCommonAncestor(root.left,p,q); // 如果两个值都大于根节点，说明祖先在右子树一侧 else if(p>root.val && q>root.val) return l...

先求出每一个结点的高度->getHeight(root) 递归地判断是否为平衡二叉树->isBalanced(root) function IsBalanced_Solution(pRoot) { function getHeight(root){ if(root == null) return 0; root.height = Math.max(getHeight(root.left), getHeight(root.right)) + 1; return root.height; } function isBalanced(root){ ...

思路：借助层序遍历 只有x,x,x,#,#,#这样的才是完全二叉树 如果出现x,#,y,#,#,#或者x,#,#,x,#,#,#证明不是完全二叉树 碰到第一个#的时侯令flag=true 如果再次碰到非#结点，且flag=true时候，说明不是完全二叉树 function isCompleteTree( root ) { let queue = []; queue.push(root); let flag = false; while(queue.length){//队列不为空时 const node = queue.shift();//取出第一个 if(nod...

第一种方法：二叉搜索树的中序遍历一定是递增的,只需判断中序遍历的数组即可 function isValidBST( root ) { function inOrder(root){ if(root==null) return; inOrder(root.left); ans.push(root.val); inOrder(root.right); } let ans = []; inOrder(root); for(let i=0;i+1<ans.length;i++){ if(ans[i]>ans[...

递归 function Mirror( pRoot ) { if(pRoot == null) return; let tmp = pRoot.left; pRoot.left = pRoot.right; pRoot.right = tmp; Mirror(pRoot.left); Mirror(pRoot.right); return pRoot; } module.exports = { Mirror : Mirror };

递归 没别的 function mergeTrees( t1 , t2 ) { if(t2==null) return t1; if(t1==null) return t2; //此时t1和t2均不为null t1.val += t2.val; t1.left = mergeTrees(t1.left,t2.left); t1.right = mergeTrees(t1.right,t2.right); return t1; } module.exports = { mergeTrees : mergeTrees };

递归 条件：p1.val == p2.val && compare(p1.left,p2.right) && compare(p1.right,p2.left) function isSymmetrical(pRoot) { function compare(p1,p2){ if(p1==null && p2==null) return true; if(p1==null || p2==null) return false; return p1.val == p2.val && ...

参考26题二叉树的层序遍历 只需判断level的奇偶，从而决定使用push方法还是unshift方法 function Print(pRoot) { function preOrder(root,level){ if(root==null) return; if(level >= res.length) res.push([]); if(level%2)//奇数 res[level].unshift(root.val); else//偶数 res[level].push(root.val); pr...

抄的题解 递归(前序遍历) 主要思路：前序遍历，中、左、右 左边的节点一定先于右边节点遍历到，加入至对应的数组中，满足层序遍历的要求； 要点： 1、利用一个level变量标记当前递归的深度，将节点的值push到当前深度的数组的后面； 2、level变量大于res数组的size，说明第一次进入二叉树本层，对res扩容； 扩展： 前序：中、左、右 中序：左、中、右 后续：左、右、中 三种遍历都是左边节点一定比右边节点先遍历到，那么push_back至对应深度的数组次序也一定与层次遍历一致；所以针对此方法，中序、后序一样可以实现层次遍历。 对示例1模拟前序遍历，如下图所示： function le...

正确的 function hasPathSum( root , sum ) { if(root==null) return false; if(sum==root.val && root.left==null && root.right==null) return true; return hasPathSum(root.right,sum-root.val) || hasPathSum(root.left,sum-root.val); } 错误的 {},0这样的测试用例过不去，我觉得emmm过得去过不去都可以 function hasPat...

没什么可说的，递归求深度，空返回0，否则返回max(左子树，右子树)+1 function maxDepth( root ) { if(root == null) return 0; return Math.max( maxDepth(root.left), maxDepth(root.right) ) + 1; } module.exports = { maxDepth : maxDepth };

后序 function postorderTraversal( root ) { function postOrder(root){ if(root == null) return; postOrder(root.left); postOrder(root.right); res.push(root.val); } let res = []; postOrder(root); return res; } module.exports = { postorderTraversal : postord...

递归 function inorderTraversal( root ) { function inOrder(root){ if(root == null) return; inOrder(root.left); ans.push(root.val); inOrder(root.right); } let ans = []; inOrder(root); return ans; } module.exports = { inorderTraversal : inorderTraversal };

注意： 1.preorderTraversal只是充当函数入口，不然递归的时候无法正确返回数组 2. function preorderTraversal( root ) { function preOrder(root){ if(root == null) return; res.push(root.val); preOrder(root.left); preOrder(root.right); } let res = []; preOrder(root); return res; } module.exports = { pre...