hot100之二叉树下

未分类 5小时前程序员胖胖胖虎阿

3 0 0

二叉树的右侧观察(199)

class Solution {
    List<Integer> result = new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
        dfs(root, 0);
        return result;
    }
    private void dfs(TreeNode node, int level){
        if (node == null) return;

        if (result.size() == level){
            result.add(node.val);
        }

        dfs(node.right, level+1);
        dfs(node.left, level+1);
    }
}

分析
因为每一层只需要一个节点，所以通过深度level来进行限制

将二叉树转化为链表结构(114)

class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;

        flatten(root.left);
        flatten(root.right);
        TreeNode leftPart = root.left;
        TreeNode rightPart = root.right;

        root.left = null;
        root.right = leftPart;
        TreeNode current = root;

        while (current.right != null){
            current = current.right;
        }current.right = rightPart;

    }
}

分析
把左子树截断后放置到右端位置，接着将右子树连接到左子树的末尾处，由于递归的特性，左子树必然是链表形态

依据前序和中序遍历序列构建二叉树(105)

class Solution {
    Map<Integer, Integer> indexMap;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int length = preorder.length;
        indexMap = new HashMap<>();
        for (int i = 0; i < length; i++){
            indexMap.put(inorder[i], i);
        }

        return dfs(preorder, 0, length, 0, length);
    }

    private TreeNode dfs(int[] preorder, int startPre, int endPre, int startIn, int endIn){
        if (startPre == endPre) return null;

        int leftSubtreeSize = indexMap.get(preorder[startPre]) - startIn;
        TreeNode leftNode = dfs(preorder, startPre+1, startPre+1+leftSubtreeSize, startIn, startIn+leftSubtreeSize);
        TreeNode rightNode = dfs(preorder, startPre+1+leftSubtreeSize, endPre, startIn+1+leftSubtreeSize, endIn);
        return new TreeNode(preorder[startPre], leftNode, rightNode);
    }
}

分析
以前序遍历确定根节点，然后切分中序遍历的左右子树来进行构建

路径总和问题(437)

class Solution {
    Map<Long, Integer> prefixSumMap = new HashMap<>();
    int total;
    public int pathSum(TreeNode root, int target) {
        prefixSumMap.put(0L,1);
        dfs(root, target, 0L);
        return total;
    }

    private void dfs(TreeNode node, int targetSum, long currentSum){
        if (node == null) return;
        currentSum += node.val;
        if (prefixSumMap.containsKey(currentSum - targetSum)) total +=prefixSumMap.get(currentSum - targetSum);
        prefixSumMap.put(currentSum, prefixSumMap.getOrDefault(currentSum, 0)+1);
        dfs(node.left, targetSum, currentSum);
        dfs(node.right, targetSum, currentSum);
        prefixSumMap.put(currentSum, prefixSumMap.get(currentSum)-1);
    }
}

分析
同样是一道运用前缀和思路来解决的题目

二叉树的最近共同祖先查找(236)

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode pNode, TreeNode qNode) {
        if (root == null || pNode == root || qNode == root) return root;

        TreeNode leftChild = lowestCommonAncestor(root.left, pNode, qNode);
        TreeNode rightChild = lowestCommonAncestor(root.right, pNode, qNode);

        if (leftChild == null && rightChild == null) return null;
        if (leftChild != null && rightChild != null) return root;

        return leftChild != null ? leftChild : rightChild;

    }
}

分析
寻找子节点并向上返回，当两个节点还未相遇时继续向上返回
感悟
在处理二叉树相关题目时，需留意需要返回给父节点的元素情况

二叉树中的最大路径值计算(124)

class Solution {
    int maxValue = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return maxValue;
    }
    private int dfs(TreeNode node){
        if (node == null) return 0;

        int leftMax = Math.max(dfs(node.left), 0);
        int rightMax = Math.max(dfs(node.right), 0);

        maxValue = Math.max(maxValue, leftMax+ node.val + rightMax);
        return Math.max(leftMax, rightMax) + node.val;
    }
}