LeetCode(力扣)答案解析（二）

我们可以看到，p是指向链表中第一个元素，q是指向链表中第二个元素，那么，我们要反转链表，原来第一个链表节点就应该变成链表最后一个节点，所以第一步我就将p.next指向null。第二步，我用一个临时变量t指向q.next，用意是用来储存还没反转链表的最开始的节点，然后，让q.next指向p，那么第一个节点，和第二个节点就局部反转了。第三步，我们还需要将p指向q，q再指向t，然后重复上述步骤，我们就可以将链表反转过来了。

解法二（递归）

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    // 递归终止条件
    if (!head || !head.next) {
        return head;
    }
    var q = head.next;
    var p = reverseList(q);
    q.next = head;
    head.next = null;
    return p;
};

在这里，我想强调的是：任何的递归程序都可以改写成迭代形式，反之也成立。

104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7]

返回最大深度为3。

解法一（递归）

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if (root) {
        var leftMax = maxDepth(root.left),
              rightMax = maxDepth(root.right);
        return Math.max(leftMax, rightMax) + 1;
    } else {
        return 0;
    }
};

这里使用的是递归方式。要求这个树最大的层数，那么，我们只需要求出左子树和右子树最大层数的一方 + 1即可，这里的1是指当前层级。

解法二 (迭代 + 栈 + 深度优先搜索)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if (!root) return 0;
    var st = [], top = -1;
     // 根节点入栈
     st[++top] = root;
     // 记录最大的层数
     var maxLevel = 1;
     root.level = 1;
     while (top != -1) {
         // 获取栈顶节点 && 出栈 （先根遍历）
         var node = st[top--],
             level = node.level;
         if (node.right) {
             st[++top] = node.right;
             st[top].level = level + 1;
             maxLevel < level + 1  && (maxLevel = level + 1);
         }
         if (node.left) {
             st[++top] = node.left;
             st[top].level = level + 1;
             maxLevel < level + 1 && (maxLevel = level + 1);
         }
     }
     return maxLevel;
};

这里会让每一个节点有一个额外的存储属性：level，来记录每一个节点的所在层数，然后与已知最大的层数对比即可得出结果。

Checkson / blog

LeetCode(力扣)答案解析（二） #6

20. 有效的括号

206. 反转链表

104. 二叉树的最大深度