每日一念
改掉自己想到哪写哪的坏习惯

二叉树

二叉树的中序遍历

class Solution {
    /**
        中序遍历
        左 - 中 - 右
     */
    private List<Integer> res =  new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root == null) {
            return res;
        }
        tranverse(root);
        return res;
    }
    public void tranverse(TreeNode node) {
        if(node == null) {
            return;
        }
        tranverse(node.left);
        res.add(node.val);
        tranverse(node.right);
    }
}

二叉树的最大深度

class Solution {
    /**
        比较左右子树深度，取最大值，还要加上root的1
     */
    int max = 0;
    public int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return tranverse(root);
    }
    public int tranverse(TreeNode node) {
        if(node == null) {
            return 0;
        }
        int left = tranverse(node.left);
        int right = tranverse(node.right);
        max = Math.max(left, right) + 1;
        return max;
    } 
}

翻转二叉树

class Solution {
    /**
        递归的每一层在干什么
        在交换结点
     */
    public TreeNode invertTree(TreeNode root) {
        tranverse(root);
        return root;
    }
    public void tranverse(TreeNode node) {
        if(node == null) {
            return;
        }
        TreeNode temp = null;
        temp = node.left;
        node.left = node.right;
        node.right = temp;
        tranverse(node.left);
        tranverse(node.right);
    }
}

对称二叉树

class Solution {
    /**
        每一层在干什么？
        判断左子树结点和右子树结点是否值相同
     */
    public boolean isSymmetric(TreeNode root) {
        if(root == null) {
            return true;
        }
        return tranverse(root.left, root.right);
    }
    public boolean tranverse(TreeNode left, TreeNode right) {
        if(left == null && right != null) {
            return false;
        }
        if(left != null && right == null) {
            return false;
        }
        if(left == null && right == null) {
            return true;
        }
        if(left.val != right.val) {
            return false;
        }
        boolean l = tranverse(left.left, right.right);
        boolean r = tranverse(left.right, right.left);
        return l && r;
    }

}

二叉树的直径

class Solution {
    /**
        
     */
    int maxlen = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        tranverse(root);
        return maxlen;
    }
    public int tranverse(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int left = tranverse(root.left);
        int right = tranverse(root.right);
        maxlen = Math.max(left + right, maxlen);
        return Math.max(left, right) + 1;
    }
}

二叉树的层序遍历

class Solution {
    /**
        每一层保存root结点的值
     */
    List<List<Integer>> res = new ArrayList();
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null) {
            return res;
        }
        tranverse(root, 0);
        return res;
    }
    public void tranverse(TreeNode root, int depth) {
        if(root == null) {
            return;
        }
        if(res.size() <= depth) {
            res.add(new ArrayList<>());
        }
        res.get(depth).add(root.val);
        tranverse(root.left, depth + 1);
        tranverse(root.right, depth + 1);
    }
}

将有序数组转化为二叉搜索树

class Solution {
    /**
        每一层要做什么
        提取目前nums的根节点，建立左右子树
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums == null || nums.length == 0) {
            return null;
        }
        return tranverse(nums, 0, nums.length - 1);
    }
    public TreeNode tranverse(int[] nums, int start, int end) {
        if(start > end) {
            return null;
        }
        int mid = (start + end) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = tranverse(nums, start, mid - 1);
        root.right = tranverse(nums, mid + 1, end);
        return root;
    }
}

验证二叉搜索树

class Solution {
    /**
        每层在做什么
        可以类比前面将nums分段的，这题是在比较root.val和min、max
     */
    public boolean isValidBST(TreeNode root) {
        return tranverse(root, null, null);
    }

    public boolean tranverse(TreeNode root, Integer min, Integer max) {
        if(root == null) {
            return true;
        }
        if((min != null && root.val <= min) || (max != null && root.val >= max)) {
            return false;
        }
        boolean left = tranverse(root.left, min, root.val);
        boolean right = tranverse(root.right, root.val, max);
        return left && right;
    }
}

二叉搜索树中第k小的元素

class Solution {
    /**
        简单朴素的想法
        将所有元素装到list里面，排序后找出第k-1个元素
     */
    List<Integer> list = new ArrayList<>();
    public int kthSmallest(TreeNode root, int k) {
        tranverse(root);
        Collections.sort(list);
        return list.get(k - 1);
    }
    public void tranverse(TreeNode root) {
        if(root == null) {
            return;
        }
        list.add(root.val);
        tranverse(root.left);
        tranverse(root.right);
    }
}

二叉树的右视图

class Solution {
    /**
        每一层在做什么？
        先右子树depth++，再左子树depth--
        res.size() < depth时，没存这层的结点值，需要存一下
     */
    List<Integer> res = new ArrayList<>();
    int depth = 0;
    public List<Integer> rightSideView(TreeNode root) {
        tranverse(root);
        return res;
    }
    public void tranverse(TreeNode root) {
        if(root == null) {
            return;
        }
        depth++;
        if(res.size() < depth) {
            res.add(root.val);
        }
        tranverse(root.right);
        tranverse(root.left);
        depth--;
    }
}

二叉树展开为链表

class Solution {
    /**
        每一层在干什么？
        将左子树结点移到右子树root.right
        右子树移到root右子树的最后结点.right
            2
           /  \
          3    4

          2
           \
            3    4

          2
           \
            3
             \
              4

     */
    public void flatten(TreeNode root) {
        if(root == null) {
            return;
        }

        flatten(root.left);
        flatten(root.right);

        TreeNode node_left = root.left;
        TreeNode node_right = root.right;

        root.left = null;
        root.right = node_left;

        TreeNode newRoot = root;
        while(newRoot.right != null) {
            newRoot = newRoot.right;
        }
        newRoot.right = node_right;
        
    }
}

从前序和中序遍历构造二叉树

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return tranverse(preorder, 0, preorder.length - 1,
         inorder, 0, inorder.length - 1);
    }
    public TreeNode tranverse(int[] preorder, int preStart, int preEnd,
     int[] inorder, int inStart, int inEnd) {
        if(preStart > preEnd) {
            return null;
        }
        int rootValue = preorder[preStart];
        TreeNode root = new TreeNode(rootValue);
        int rootIndex = 0;
        for(int i = inStart; i <= inEnd; i++) {
            if(inorder[i] == rootValue) {
                rootIndex = i;
            }
        }
        int leftLen = rootIndex - inStart;
        int rightLen = inEnd - rootIndex;
        root.left = tranverse(preorder, preStart + 1, preStart + leftLen
        , inorder, inStart, rootIndex - 1);
        root.right = tranverse(preorder, preStart + leftLen + 1, preEnd
        , inorder, rootIndex + 1, inEnd);
        return root;
     }
}

路径总和III

class Solution {
    /**
    	每一层在做什么？
    	dps1到一层的根节点，dps2往下搜寻有没有和=targertSum的
        需要注意测试用例
        int转成long类型
     */
    int ans = 0;
    int target = 0;
    public int pathSum(TreeNode root, int targetSum) {
        target = targetSum;
        dps1(root);
        return ans;
    }
    public void dps1(TreeNode root) {
        if(root == null) {
            return;
        }
        dps2(root, root.val);
        dps1(root.left);
        dps1(root.right);
    }
    public void dps2(TreeNode root, long t) {
        if(t == target) {
            ans++;
        }
        if(root.left != null) {
            dps2(root.left, root.left.val + t);
        }
        if(root.right != null) {
            dps2(root.right, root.right.val + t);
        }
    }
}

二叉树的最近公共祖先

class Solution {
    /**
        每一层都在做什么？
        left记录找到的最近左祖先，right记录找到的最近右祖先

        left right都有 -- 祖先root
        只在left -- 返回left
        只在right -- 返回right
        都没有 -- 返回null
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left != null && right != null) {
            return root;
        }
        else if(left != null) {
            return left;
        }
        else if(right != null) {
            return right;
        }
        else {
            return null;
        }
    }
}

二叉树中最大路径和

class Solution {
    /**
        难题直接灵神yyds
        看了灵神的题解，其实和最大深度差不多（真的 QAQ
     */
    int ans = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dps(root);
        return ans;
    }
    public int dps(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftValue = dps(root.left);
        int rightValue = dps(root.right);
        ans = Math.max(ans, leftValue + rightValue + root.val);
        return Math.max(Math.max(leftValue, rightValue) + root.val, 0);
    }
}