二叉樹左下角的值

題目鏈接

https://programmercarl.com/0513.%E6%89%BE%E6%A0%91%E5%B7%A6%E4%B8%8B%E8%A7%92%E7%9A%84%E5%80%BC.html

思路

遞歸法贫导，需要回溯深度序调，只有深度最大值有變化時(shí)才會(huì)記錄左下角

    private int maxDepth = 0;
private int res = 0;
public int findBottomLeftValue(TreeNode root) {
    
     find(root, 1);
     return res;
}

public void find(TreeNode node, int depth) {
    if(node.left == null && node.right == null) {
        if(depth > maxDepth) {
            maxDepth = depth;
            res =  node.val;
        }
    }
    if(node.left != null) {
        find(node.left, depth + 1);
    }
    if(node.right != null) {
    find(node.right, depth + 1);

    }
    
}

路徑總和

題目鏈接

https://programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html

思路

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

}

private void hasPathSu(TreeNode node, int targetSum) {
    if(node.left == null && node.right == null) {
        if(!hasPathSum) {
            hasPathSum = targetSum == node.val;
        }
    }
    if(node.left!= null) {
        hasPathSu(node.left, targetSum - node.val);
    }
    if(node.right != null) {
        hasPathSu(node.right, targetSum - node.val);
    }
}


    private List<List<Integer>> res = new ArrayList();
private List<Integer> path = new ArrayList();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if(root ==null) {
            return res;
        }
        pathSum1(root, targetSum);
        return res;
    }

    private void pathSum1(TreeNode root, int targetSum) {
        path.add(root.val);
        if(root.left == null && root.right == null) {
            if(root.val == targetSum) {
                res.add(new ArrayList<>(path));
            }
        }
        if(root.left != null) {
            pathSum1(root.left, targetSum - root.val);
            path.remove(path.size() - 1);
        }
        if(root.right != null) {
            pathSum1(root.right, targetSum - root.val);
            path.remove(path.size() - 1);

        }
    }

構(gòu)造二叉樹

思路挺簡單的，記住區(qū)間左閉右開 保持這一原則

    private Map<Integer, Integer> map = new HashMap();
public TreeNode buildTree(int[] inorder, int[] postorder) {
    for(int i = 0; i < inorder.length; i++) {
        map.put(inorder[i], i);
    }
    return buildTree1(inorder, 0, inorder.length, postorder, 0, postorder.length);
}

private TreeNode buildTree1(int[] inorder, int inBegin, int inEnd, int[] postorder, int poBegin, int poEnd) {
    if(inBegin == inEnd) {
        return null;
    }
    int mid = map.get(postorder[poEnd - 1]);
    TreeNode root = new TreeNode(inorder[mid]);
    root.left = buildTree1(inorder, inBegin, mid, postorder, poBegin, poBegin + mid - inBegin);
    root.right = buildTree1(inorder, mid+1, inEnd, postorder, poBegin + mid - inBegin, poEnd-1);
    return root;
}