invert binary tree（翻转二叉树）

思考

首先要翻转整棵二叉树肯定需要对每个非叶子节点的子节点进行翻转所以就涉及到树的遍历，那么采取哪种遍历方式呢，【后续遍历】，为什么是后续遍历呢。那就分析一下前序和中序存在哪些问题。

• 前序遍历

  思考一下如果是前序遍历首先遍历的节点就是根节点。那么会出现什么情况，首先遍历到根节点交换其两个子节点，随后应该遍历的是根节点的左子节点，那么问题来了。现在的左子节点还是左子节点吗？显然不是。所以不能采用前序遍历

• 中序遍历

  如果是中序遍历首先遍历到的是最左侧的叶子节点，但叶子节点不需要交换所以约定通过中序遍历能遍历到的第一个非叶子节点为当前节点，那么交换当前节点的两个子节点。根据中序遍历下一个要遍历的就是当前节点的父节点，交换父节点的左右节点，然后遍历到父节点的右子节点。这时问题出现了，右子节还是开始的右子节点吗？显然不是，在对父节点进行翻转时已经将右子节点交换为了左子节点。所以不能采用中序遍历

再来看后续遍历，左右根，它总会在左右两个节点操作完成后再翻转父节点所以不存在上面两种情况。

附上代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null){
            return root;
        }else{
            invertTree(root.left);
            invertTree(root.right);
            return invert(root);    
        }
    }
    public TreeNode invert(TreeNode node){
        TreeNode temp =node.left;
        node.left = node.right;
        node.right = temp;
        return node;
    }
}

附leetcode该问题执行效率最高的代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null){
            return null;
        }
        TreeNode right = invertTree(root.right);
        TreeNode left = invertTree(root.left);
        
        root.right = left;
        root.left =right;
        return root;
    }
}

max consecutive ones（查找数组中最多元素连续出现次数，数组中只会出现0和1）

思考

首先肯定是要遍历数组，并且可以有这么一个事实，一旦遍历元素遇到零最长连续元素也就终止了。后面需要从0开计。

那么就可以有两个变量，一个用于储存上一个最长连续元素(lastNum)，一个用于计算当前最长连续元素(currentNum)。一旦计算当前最长元素长度被终止（即遇到了0）就比较currentNum和lastNum，如果currentNum>lastNum就把currentNum赋值给lastNum并重置currentNum为0用于下一次计算。最后考虑数组只有一个1的情况[1]此时lastNum还没有被比较。需要返回currentNum和lastNum中较大者

附代码：

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int len = nums.length;
        int lastNum = 0;
        int currentNum = 0;
        for(int i=0;i<len;i++){
            if(nums[i]==1){
                currentNum++;
            }else{
                if(currentNum>lastNum){
                    lastNum = currentNum;
                }
                currentNum=0;
            }
        }
        return currentNum>lastNum?currentNum:lastNum;
    }
}

Find Numbers with Even Number of Digits （查找数组中数字位数为偶数的元素个数）

思考

首先肯定也要遍历数组，其次要思考的问题是怎样判断当前元素位数是否为偶数，涉及到位数首先就应该想到除10以及10的倍数。那么就有如下思路，用当前元素依次除10，100，1000，...依次类推。只要结果不等于0就继续向后除。用一个变量count记录除了多少次，那么count就是当前元素的位数。再用count%2就知道该元素是不是偶位数数字了

附代码：

class Solution {
    public int findNumbers(int[] nums) {
        int len = nums.length;
        int count = 0;
        for(int i=0;i<len;i++){
            int digits = 0;
            int ratios = 10;
            while(true){
                digits++;
                if(nums[i]/ratios==0){
                    break;
                }
                ratios=ratios*10;
            }
            if(digits%2==0){
                count++;
            }
        }
        return count;
    }
}

一点一滴汇江河

---

最后：大幻梦森罗万象狂气断罪眼\ (•◡•) /