代码随想录算法训练营第十八天

LeetCode 513.找到树最左下角的值

class Solution {
    public int findBottomLeftValue(TreeNode root) {

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        TreeNode node = root;
        List<List<Integer>> ans = new LinkedList<>();

        while (!queue.isEmpty()) {
            int size = queue.size();

            List<Integer> values = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                node = queue.poll();
                values.add(node.val);

                if (node.left != null) {
                    queue.add(node.left);
                }

                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            ans.add(values);
        }
        List<Integer> lastLevel = ans.get(ans.size() - 1);
        return lastLevel.get(0);
    }
}

层序遍历的思路很简单，找到所有层的value list， 返回最后一层最左侧元素.

LeetCode 112. 路经总和

因为题目只要求一个布尔的结果，即这样的路径是否存在，所以不需要考虑回溯的事情

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }

        if (root.val == targetSum && root.left == null && root.right == null) {
            return true;
        }

        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
    }
}

LeetCode 113.路经总和-ii

因为题目要求返回所有可能的路径，在前一题代码的基础上进行少许修改，加入backtrack即可

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> ans = new LinkedList<>();
        preorder(ans, new LinkedList<>(), root, targetSum);
        return ans;
    }

    private void preorder (List<List<Integer>> ans, List<Integer> path, TreeNode node, int targetSum){
        
        // exitrance
        if (node == null) {
            return;
        }

        // add the val of the node into path
        path.add(node.val);

        // if this is a leaf node and its val is equals to target, record this path
        if (node.val == targetSum && node.left == null && node.right == null) {
          	// note here, we cannot directly add path list to the ans, as it is just
            // a temp container and would be changed during next track
            List<Integer> validPath = new LinkedList<>();
            validPath.addAll(path);
            ans.add(validPath);
        }

        // if there are children nodes, recursivelly call this func
        if (node.left != null) {
            preorder(ans, path, node.left, targetSum - node.val);
            // backtrack
            path.remove(path.size() - 1);
        }

        if (node.right != null) {
            preorder(ans, path, node.right, targetSum - node.val);
            // backtrack
            path.remove(path.size() - 1);
        }
    }
}

LeetCode 105.从前序和中序遍历序列构造二叉树

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildmyThree(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }

    public TreeNode buildmyThree(int[] preorder, int preBeginIndex, int preEndIndex, int[] inorder, int inBeginIndex, int inEndIndex) {
        
        // when [preBeginIndex, preEndIndex) has no element, return null;
        if (preBeginIndex >= preEndIndex) {
                return null;
        }

        int rootValue = preorder[preBeginIndex];
        TreeNode root = new TreeNode(rootValue);

        // left branch
        // the key here is how to make sure the next range of preorder array and inorder array
        // deal with the inorder array first, as we know where to devide it into two partitions
        int devideInorderIndex = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == rootValue) {
                devideInorderIndex = i;
                break;
            }
        }

        // culculate the leftTreeSize to handle the preOrder array starting Index and size
        int leftTreeSize = devideInorderIndex - inBeginIndex;

        TreeNode leftNode = buildmyThree(preorder, preBeginIndex + 1, preBeginIndex + leftTreeSize + 1, inorder, inBeginIndex, devideInorderIndex);
        root.left = leftNode;

        // right branch
        TreeNode rightNode = buildmyThree(preorder, preBeginIndex + leftTreeSize + 1, preEndIndex, inorder, devideInorderIndex + 1, inEndIndex);
        root.right = rightNode;

        return root;
    }
}

LeetCode 106.从中序和后序遍历构造二叉树

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return buildmyTree(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }

    private TreeNode buildmyTree(int[] inorder, int inStartIndex, int inEndIndex, int[]postorder, int postStartIndex, int postEndIndex) {
        
        // if there is no elements in [inStartIndex, inEndIndex) then return
        if (inStartIndex >= inEndIndex) {
            return null;
        }

        // the last element in postorder is the root of the whole tree
        int rootValue = postorder[postEndIndex - 1];

        TreeNode root = new TreeNode(rootValue);

        // find the index of rootValue in inorder array to divide the inOrder array into two partitions

        int rootValueIndexAtInOrder = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == rootValue) {
                rootValueIndexAtInOrder = i;
                break;
            }
        }

        int leftPostOrderArraySize = rootValueIndexAtInOrder - inStartIndex;

        // the next step is recursively call this function to get the left node and right node
        root.left = buildmyTree( inorder, inStartIndex,  rootValueIndexAtInOrder, postorder, postStartIndex, postStartIndex + leftPostOrderArraySize);

        root.right = buildmyTree( inorder, rootValueIndexAtInOrder + 1, inEndIndex, postorder, postStartIndex + leftPostOrderArraySize, postEndIndex - 1);

        return root;
    }
}

这两道题其实有异曲同工之妙，其核心在于，仔细观察一颗二叉树的前，中和后序遍历会发现，前序遍历的首个元素是整个二叉树的root，后续遍历的最后一个元素是二叉树的root，由此就知道该怎么进一步对中序遍历的数组进行划分然后递归的解决子问题。 注意，在递归中维持不变量.