Ahri-珊

day20将分享LeetCode算法题226，231，234。（时间过得好快0.0）

LeetCode

今天的三道题涉及到二叉树、递归还有链表。

226. Invert Binary Tree

对二叉树求逆。

心路历程

1.方法：递归

2.对二叉树进行层次遍历

3.将当前节点的左右子节点交换

4.子节点执行递归函数

5.递归出口：遍历完所有节点

代码：

var invertTree = function(root) {
    if(!root)
        return null;
    var temp;
    temp = root.left;
    root.left = root.right;
    root.right = temp;
    invertTree(root.left);
    invertTree(root.right);
    return root;
};

231. Power of Two

判断这个数是不是2的幂

心路历程

1.判断一个数是否是2的幂，只需判断它是否能一直被2整除直到结果为1

2.方法：递归

3.n能被2整除将n/2作为下一次递归的参数，若n等于1，返回true

4.n不能被2整除了，直接返回false

5.特殊：n为不能作为被除数的0返回false

代码：

var isPowerOfTwo = function(n) {
    if(n==0)
        return false;
    if(n==1)
        return true;
    if(n%2==0
        return isPowerOfTwo(n/2);
    else
        return false;
};

234. Palindrome Linked List

判断这是不是一个回文链表

心路历程

1.我的第一反应就是把链表倒过来，值和原始列表相等就是回文链表

2.遍历链表，在对链表求逆的时候将原来链表的值存入数组（好像还不如耍赖直接存数组判断数组是不是回文）

3.比较倒过来的链表的值与数组中对应值是否相等，相等返回true，不等返回false

代码：

var isPalindrome = function(head) {
    var copy = [];
    var prev = null;
    var next = null;
    while(head)
        {
            copy.push(head.val);
            next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
    var i = 0;
    while(prev)
        {
            if(prev.val==copy[i])
                {
                    prev = prev.next;
                    i++;
                }
            else
                return false;
        }
    return true;
};

END