本文共 3717 字，大约阅读时间需要 12 分钟。

树的子结构

• 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

/* function TreeNode(x) {    this.val = x;    this.left = null;    this.right = null;} */function HasSubtree(pRoot1, pRoot2){    if(!pRoot1 || !pRoot2) {        return false;    }    return isSubTree(pRoot1, pRoot2) || HasSubtree(pRoot1.left, pRoot2) || HasSubtree(pRoot1.right, pRoot2);}function isSubTree(root1, root2) {    if(!root2) {
  //Tree2为空，则说明第二棵树遍历完了，即匹配成功        return true;    }    if(!root1) {
  //tree1为空有两种情况（1）如果tree1为空&&tree2不为空说明不匹配（2）如果tree1为空，tree2为空，说明匹配。        return false;    }    if(root1.val == root2.val) {        return isSubTree(root1.left, root2.left) && isSubTree(root1.right, root2.right);     }else {        return false;    }}

思路解析：

1、首先设置标志位result = false，因为一旦匹配成功result就设为true， 剩下的代码不会执行，如果匹配不成功，默认返回false 2、递归思想，如果根节点相同则递归调用isSubTree()， 如果根节点不相同，则判断tree1的左子树和tree2是否相同， 再判断右子树和tree2是否相同 3、注意null的条件，HasSubTree中，如果两棵树都不为空才进行判断， isSubTree中，如果Tree2为空，则说明第二棵树遍历完了，即匹配成功， tree1为空有两种情况（1）如果tree1为空&&tree2不为空说明不匹配， （2）如果tree1为空，tree2为空，说明匹配。

二叉树的镜像

• 操作给定的二叉树，将其变换为源二叉树的镜像。

/* function TreeNode(x) {    this.val = x;    this.left = null;    this.right = null;} */function Mirror(root){    if(root === null) {        return;    }    var temp = root.left;    root.left = root.right;    root.right = temp;    Mirror(root.left);    Mirror(root.right);}

思路解析：

判断树是否为空，然后交换左右子树，最后递归交换左右子树。

顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

function printMatrix(matrix){    var row=matrix.length;    var col=matrix[0].length;    var res=[];    if(row==0||col==0){        return res;    }    var left=0,        top=0,        right=col-1,        bottom=row-1;    while(left<=right&&top<=bottom){        for(var i=left;i<=right;i++)            res.push(matrix[top][i]);        for(var i=top+1;i<=bottom;i++)            res.push(matrix[i][right]);        if(top!=bottom)            for(var i=right-1;i>=left;i--)                res.push(matrix[bottom][i]);        if(left!=right)            for(var i=bottom-1;i>top;i--)                res.push(matrix[i][left]);        left++,top++,right--,bottom--;    }    return res;}

思路解析：

用左上和右下的坐标定位出一次要旋转打印的数据，一次旋转打印结束后，往对角分别前进和后退一个单位。

定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。

var stack = [];function push(node){
       stack.push(node);}function pop(){
       return stack.length==0 ? null : stack.pop();}function top(){
       return stack.length==0 ? null : stack[0];}function min(){
       return stack.length == 0 ? null : Math.min.apply(null, stack);}

思路解析：

JS中数组底层是基于栈实现，因此本题目可根据此属性直接实现，但是注意此题的空值判断。

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

function IsPopOrder(pushV, popV){    var stack = [];    var index = 0;    for(var i=0; i

思路解析：

借用一个辅助的栈，遍历压栈顺序，先讲第一个放入栈中，这里是1，然后判断栈顶元素是不是出栈顺序的第一个元素，这里是4，很显然1≠4，所以我们继续压栈，直到相等以后开始出栈，出栈一个元素，则将出栈顺序向后移动一位，直到不相等，这样循环等压栈顺序遍历完成，如果辅助栈还不为空，说明弹出序列不是该栈的弹出顺序。 举例： 入栈1,2,3,4,5 出栈4,5,3,2,1 首先1入辅助栈，此时栈顶1≠4，继续入栈2 此时栈顶2≠4，继续入栈3 此时栈顶3≠4，继续入栈4 此时栈顶4＝4，出栈4，弹出序列向后一位，此时为5，,辅助栈里面是1,2,3 此时栈顶3≠5，继续入栈5 此时栈顶5=5，出栈5,弹出序列向后一位，此时为3，,辅助栈里面是1,2,3 …. 依次执行，最后辅助栈为空。如果不为空说明弹出序列不是该栈的弹出顺序。

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

/* function TreeNode(x) {    this.val = x;    this.left = null;    this.right = null;} */function PrintFromTopToBottom(root){    var arr = [];    var data = [];    if(root != null) {        arr.push(root);    }    while(arr.length > 0) {        var node = arr.shift();        data.push(node.val);        if(node.left != null) {            arr.push(node.left);        }        if(node.right != null) {            arr.push(node.right);        }    }    return data;}

思路解析：

按层序遍历二叉树

转载地址：https://blog.csdn.net/zzl819954692/article/details/80091546 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！