Day18 二叉树路径 | 构建二叉树

今日内容

● 513.找树左下角的值

● 112. 路径总和 113.路径总和ii

● 106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树

513. 找树左下角的值

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

只需要记录最后一行第一个节点的数值就可以了。

非递归的方式

/**
 * Definition for a binary tree node.
 * type TreeNode quruct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findBottomLeftValue(root *TreeNode) int {
    // 思路：采用层序遍历的方法，遍历每一层都更新 最左下的 值
    if root == nil {
        return 0
    }
    qu := make([]*TreeNode, 0)
    res := 0
    qu = append(qu, root)
    for len(qu) != 0 {
        top := qu[0]
        res = top.Val
        size := len(qu)
        for i := 0; i < size; i ++ {
            top = qu[0]
            qu = qu[1:]            
            if top.Left != nil {
                qu = append(qu, top.Left)
            }
            if top.Right != nil {
                qu = append(qu, top.Right)
            }
        }
    }
    return res
}

递归的方式

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findBottomLeftValue(root *TreeNode) int {
    // 思路：通过一个全局变量记录最大深度，只有大于这个值才会更新结果
    if root == nil {
        return 0
    }
    res := 0
    maxDepth := math.MinInt64
    help(root, &res, &maxDepth, 0)
    return res
}
func help(root *TreeNode, res *int, maxDepth *int, depth int) {
    // 左右都为空
    if root.Left == nil && root.Right == nil {
        // 第一次达到这里的肯定是 最左的
        if depth > *maxDepth {
            *maxDepth = depth
            *res = root.Val
        }
        return
    }
    if root.Left != nil {
        depth ++
        help(root.Left, res, maxDepth, depth)
        depth --
    }
    if  root.Right != nil {
        depth ++
        help(root.Right, res, maxDepth, depth)
        depth --
    }
    return
}

C++实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        // 迭代，层序遍历，更新左节点的值
        // 记录层数，层数大于才更新
        if(root == nullptr) return 0;
        int res = 0;
        queue<TreeNode *> qu;
        qu.push(root);
        while(!qu.empty()) {
            int size = qu.size();
            for(int i = 0; i < size; i ++){
                auto top = qu.front();
                qu.pop();
                // 表示最左边的
                if(i == 0) res = top->val;
                if(top->left) qu.push(top->left);
                if(top->right) qu.push(top->right);
            }

        }
        return res;
    }


};

112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func hasPathSum(root *TreeNode, targetSum int) bool {
    // 思路：回溯。目标值不断减小，到根节点的时候等于0返回true
    if root == nil {
        return false
    }
    targetSum -= root.Val
    if root.Left == nil && root.Right == nil {
        if targetSum == 0 {
            return true
        }else {
            return false
        }
    }
    // 因为返回的是或，分别执行，所以不需要 加回来
    return hasPathSum(root.Left, targetSum) || hasPathSum(root.Right, targetSum)
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root == nullptr) return false;
        targetSum -= root->val;
        if(root->left == nullptr && root->right == nullptr) {
            if(targetSum == 0) return true;
            else return false;
        } 
        return hasPathSum(root->left, targetSum) || hasPathSum(root->right, targetSum);
        
    }
};

113. 路径总和 II

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pathSum(root *TreeNode, targetSum int) [][]int {
    // 思路：回溯。遍历当 targetSum 为0的时候加入结果集
    if root == nil {
        return nil
    }
    res := make([][]int, 0)
    list := make([]int, 0)
    help(root, targetSum, list, &res)
    return res
}

func help(root *TreeNode, targetSum int, list []int, res *[][]int) {
    if root == nil {
        return 
    }
    list = append(list, root.Val)
    targetSum -= root.Val
    // 注意这个时候 不需要返回
    if root.Left == nil && root.Right == nil && targetSum == 0 {
        tmp := make([]int, len(list))
        copy(tmp, list)
        *res = append(*res, tmp)
    }
    help(root.Left, targetSum, list, res)
    help(root.Right, targetSum, list, res)
    targetSum += root.Val
    return 
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> res;
        vector<int> tmp;
        dfs(root, res, tmp, targetSum);
        return res;
    }
    void dfs(TreeNode* root, vector<vector<int>> &res, vector<int> &tmp, int targetSum) {   
        if(root == nullptr) return;
        tmp.push_back(root->val);
        targetSum -= root->val;
        if(root->left == nullptr && root->right == nullptr && targetSum == 0) {
            res.push_back(tmp);
        }
        dfs(root->left, res, tmp, targetSum);
        dfs(root->right, res, tmp, targetSum);
        tmp.pop_back();
        return;
    }
};

106. 从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(inorder []int, postorder []int) *TreeNode {
    // 思路：将后序遍历的最后一个 元素作为 根节点，以这个来分割中序遍历
    if len(inorder) != len(postorder) || len(inorder) == 0 || len(postorder) == 0{
        return nil
    }
    val := postorder[len(postorder)-1]
    i := 0
    for ; i < len(inorder); i ++ {
        if inorder[i] == val {
            break
        }
    }
    root := &TreeNode{}
    root.Val = val
    root.Left = buildTree(inorder[:i], postorder[:i])
    root.Right = buildTree(inorder[i+1:], postorder[i:len(postorder)-1])
    return root
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(inorder.size() != postorder.size()) return nullptr;
        if(inorder.size() == 0 || postorder.size() == 0) return nullptr;

        int rootVal = postorder[postorder.size() - 1];
        int i = 0;
        for( ; i < inorder.size(); i ++ ) {
            if(inorder[i] == rootVal) break;
        }
        vector<int> inorderLeft, inorderRight, postorderLeft, postorderRight;
        for(int j = 0; j < i; j ++ ) {
            inorderLeft.push_back(inorder[j]);
            postorderLeft.push_back(postorder[j]);
        }
        for(int j = i + 1; j < inorder.size(); j ++) {
            inorderRight.push_back(inorder[j]);
            postorderRight.push_back(postorder[j - 1]);
        }
        TreeNode* root = new TreeNode(rootVal);
        root->left = buildTree(inorderLeft, postorderLeft);
        root->right = buildTree(inorderRight, postorderRight);
        return root;

    }
};

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

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(preorder []int, inorder []int) *TreeNode {
    // 思路类似
    if len(preorder) != len(inorder) || len(preorder) == 0 || len(inorder) == 0 {
        return nil
    }
    val := preorder[0]
    i := 0
    for ; i < len(inorder); i ++ {
        if inorder[i] == val {
            break
        }
    }
    root := &TreeNode{}
    root.Val = val
    root.Left = buildTree(preorder[1:i+1], inorder[:i])
    root.Right = buildTree(preorder[i+1:], inorder[i+1:])
    return root
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size() != inorder.size() || preorder.size() == 0 || inorder.size() == 0) return nullptr;
        int rootVal = preorder[0];
        int i = 0;
        for(; i < inorder.size(); i ++ ) {
            if(inorder[i] == rootVal) break;
        }
        cout << "find i = " << i << endl;
        vector<int> preorderLeft, preorderRight, inorderLeft, inorderRight;
        for(int j = 0; j < i; j ++ ) {
            preorderLeft.push_back(preorder[j + 1]);
            inorderLeft.push_back(inorder[j]);
        }
        cout << "left i = " << i << endl;
        for(int j = i + 1; j < inorder.size(); j ++ ) {
            preorderRight.push_back(preorder[j]);
            inorderRight.push_back(inorder[j]);
        }
        cout << "right i = " << i << endl;

        TreeNode* root = new TreeNode(rootVal);
        root->left = buildTree(preorderLeft, inorderLeft);
        root->right = buildTree(preorderRight, inorderRight);
        return root;
    }
};

总结

• 二叉树的路径。一题是求是否存在路径，一题是求满足条件的所有路径。第一题只需要减去根节点的值就行了，然后判断左右是否有满足的，第二题需要进行回溯，注意结束条件是节点为空，当左右节点都为空的时候不需要返回，因为会继续遍历右边，然后再进行回溯
• 构建二叉树还是非常的熟练了。只需要对前序和后序遍历进行切割即可
• 求最下最左节点的值，有点小难度，通过层序遍历的方式可以很好的解决。层序遍历使用的是队列，前序和中序非递归都是使用的栈，如果这一题使用递归还是有点麻烦的，需要比较当前的深度和最大的深度，第一次大于的时候，说明是最左的，更新值即可。这一题也有一个引申题，如果想要求最下最右的那个值应该怎么做呢？