語言：Java/C++?

513.找樹左下角的值

給定一個(gè)二叉樹的?根節(jié)點(diǎn)?root，請找出該二叉樹的?最底層?最左邊?節(jié)點(diǎn)的值。

假設(shè)二叉樹中至少有一個(gè)節(jié)點(diǎn)。

示例 1:

輸入: root = [2,1,3]
輸出: 1

示例 2:

輸入: [1,2,3,4,null,5,6,null,null,7]
輸出: 7

遞歸法

class Solution {
    int maxDepth=-1;
    int result;
    void traversal(TreeNode node, int depth){
        if(node.left==null && node.right==null){ //葉子節(jié)點(diǎn)
            if(depth>maxDepth) {
                maxDepth=depth;
                result=node.val;
            }
        }
        if(node.left!=null){
            depth++;
            traversal(node.left,depth);
            depth--;  //回溯
        }
        if(node.right!=null){
            depth++;
            traversal(node.right,depth);
            depth--;  //回溯
        }
        return;
    }
    public int findBottomLeftValue(TreeNode root) {
        traversal(root,0);
        return result;
    }
}

112.?路徑總和??

給你二叉樹的根節(jié)點(diǎn)? root?和一個(gè)表示目標(biāo)和的整數(shù)? targetSum?。判斷該樹中是否存在? 根節(jié)點(diǎn)到葉子節(jié)點(diǎn)?的路徑，這條路徑上所有節(jié)點(diǎn)值相加等于目標(biāo)和? targetSum?。如果存在，返回? true?；否則，返回? false

示例 1：

輸入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
輸出：true
解釋：等于目標(biāo)和的根節(jié)點(diǎn)到葉節(jié)點(diǎn)路徑如上圖所示。

1. 遞歸函數(shù)的參數(shù)和返回值：本題需要進(jìn)行判斷是否存在滿足條件的路徑，所以函數(shù)類型為bool，參數(shù)有根節(jié)點(diǎn)和計(jì)數(shù)器count。主函數(shù)里count傳入的是目標(biāo)值減去根節(jié)點(diǎn)的值即target-root.val，因此搜索的過程是一個(gè)做減法的過程，如果到某一個(gè)葉子節(jié)點(diǎn)減去以后剛好count=0，則說明存在滿足條件的路徑。
2. 終止條件：如果為葉子節(jié)點(diǎn)且count==0，則返回true，否則返回false
3. 單層遞歸邏輯：即然前中后都可，用前序遍歷，先用count減去當(dāng)前節(jié)點(diǎn)的值，判斷如果當(dāng)前回溯的返回值為true，則繼續(xù)返回true，回溯再把減去的當(dāng)前值加回去。

class Solution {
    boolean traversal(TreeNode node, int count){
        if(node.left==null && node.right==null && count==0) return true;
        if(node.left==null && node.right==null && count!=0) return false;
        //左
        if(node.left!=null){
            count-=node.left.val;
            if(traversal(node.left, count)) return true;  //若之前判斷有滿足條件的，直接true
            count+=node.left.val;
        }
        if(node.right!=null){
            count-=node.right.val;
            if(traversal(node.right, count)) return true;  //若之前判斷有滿足條件的，直接true
            count+=node.right.val;
        }
        return false;
    }
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root==null) return false;
        return traversal(root, targetSum-root.val);
    }
}

113.路徑總和ii

和路徑總和1不同的是這里讓給出所有符合條件的路徑，因此返回值發(fā)生了變化，不需要有返回值因?yàn)橐闅v整個(gè)樹，設(shè)置全局變量記錄路徑和結(jié)果。

class Solution {
    List<List<Integer>> res=new ArrayList<>();
    List<Integer> path =new LinkedList<>();

    void traversal(TreeNode node, int count){
        if(node.left==null && node.right == null && count==0){
            //res.add(path);
            res.add(new LinkedList<>(path));
            return;
        }
        if(node.left==null && node.right == null && count!=0) return;
        if(node.left!=null){
            path.add(node.left.val);
            count-=node.left.val;
            traversal(node.left, count);
            count+=node.left.val;
            path.removeLast();
        }
        if(node.right!=null){
            path.add(node.right.val);
            count-=node.right.val;
            traversal(node.right, count);
            count+=node.right.val;
            path.removeLast();
        }
        return;
    }

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        res.clear();
        path.clear();
        if(root==null) return res;
        path.add(root.val);
        traversal(root, targetSum-root.val);
        return res;

    }
}

106.從中序與后序遍歷序列構(gòu)造二叉樹?

根據(jù)一棵樹的中序遍歷與后序遍歷構(gòu)造二叉樹。

注意: 你可以假設(shè)樹中沒有重復(fù)的元素。

例如，給出

• 中序遍歷 inorder = [9,3,15,20,7]
• 后序遍歷 postorder = [9,15,7,20,3] 返回如下的二叉樹：

• 

1. 遞歸函數(shù)的參數(shù)和返回值：不需要有返回值，參數(shù)則是后序和中序序列
2. 終止條件：當(dāng)前序列為空
3. 單層遞歸邏輯：后序數(shù)組的最后一個(gè)元素，根據(jù)這個(gè)元素的值找到在中序數(shù)組的位置root_idx，將中序數(shù)組分為，左中序數(shù)組和右中序數(shù)組。計(jì)算左中序數(shù)組的個(gè)數(shù)，以此來確定后序數(shù)組中左后序數(shù)組的個(gè)數(shù)。將后序數(shù)組分為左后序和右后序。將后序數(shù)組中的最后一個(gè)元素去掉。

class Solution {
    Map<Integer, Integer> map;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        
        return traversal(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }
    public TreeNode traversal(int[] inorder, int inB, int inE, int[] postorder, int postB, int postE){
        if(inB >= inE || postB >= postE) return null;   //返回空樹
        map = new HashMap<>();
        for (int i=0; i<inorder.length;i++){
            map.put(inorder[i], i);    //用map來存放中序數(shù)組的值和位置，以實(shí)現(xiàn)快速查找
        }
        int rootIdx=map.get(postorder[postE-1]);   //在中序數(shù)組中查找后序的最后一個(gè)元素
        TreeNode root = new TreeNode(inorder[rootIdx]);
        int lenofLeft=rootIdx-inB;  //左中數(shù)組的個(gè)數(shù)
        root.left=traversal(inorder, inB, rootIdx, postorder, postB, postB+lenofLeft);   //保持左閉右開
        root.right=traversal(inorder, rootIdx+1, inE, postorder, postB+lenofLeft, postE-1);
        return root;
    }  
}

前序和中序的思路和上面的基本一樣，就是把取后序數(shù)組的最后一個(gè)元素?fù)Q成取前序數(shù)組的第一個(gè)元素即可。文章來源地址http://www.zghlxwxcb.cn/news/detail-832349.html

class Solution {
    Map<Integer, Integer> map;
    public TreeNode traversal(int[] preorder,int preB, int preE, int[] inorder, int inB, int inE){
            if(preE<=preB||inE<=inB) return null;
            map=new HashMap<>();
            for(int i=0; i<inorder.length;i++){
                map.put(inorder[i], i);
            }
            int rootIdx=map.get(preorder[preB]);
            TreeNode root =new TreeNode(inorder[rootIdx]);
            int lengthOfLeft=rootIdx-inB;
            root.left=traversal(preorder, preB+1, lengthOfLeft+preB+1, inorder,inB, rootIdx);
            root.right=traversal(preorder, lengthOfLeft+preB+1, preE, inorder, rootIdx+1, inE);
            return root;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return traversal(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }
}

到了這里，關(guān)于Leetcoder Day16｜ 二叉樹 part05的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！