查找两棵二叉搜索树之和

1214. 查找两棵二叉搜索树之和

给出两棵二叉搜索树的根节点 root1 和 root2 ，请你从两棵树中各找出一个节点，使得这两个节点的值之和等于目标值 Target。

如果可以找到返回 True，否则返回 False。

示例 1：

输入：root1 = [2,1,4], root2 = [1,0,3], target = 5
输出：true
解释：2 加 3 和为 5 。

示例 2：

输入：root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18
输出：false

提示：

每棵树上节点数在 [1, 5000] 范围内。
-10⁹ <= Node.val, target <= 10⁹

相似题目

两数之和 IV - 输入二叉搜索树

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

/** * 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 twoSumBSTs(TreeNode* root1, TreeNode* root2, int target) { } };

golang 解法, 执行用时: 12 ms, 内存消耗: 7.8 MB, 提交时间: 2023-10-21 22:38:48

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pre(head *TreeNode, s *[]int) {
	if head == nil {
		return
	}
	if head.Left != nil {
		pre(head.Left, s)
	}
	*s = append(*s, head.Val)
	if head.Right != nil {
		pre(head.Right, s)
	}
}

func twoSumBSTs(root1 *TreeNode, root2 *TreeNode, target int) bool {
	s1 := make([]int, 0)
	pre(root1, &s1)
	s2 := make([]int, 0)
	pre(root2, &s2)
	m := make(map[int]int, 0)
	for _, v := range s2 {
		m[v] = 1
	}
	for _, v := range s1 {
		n := target - v
		if _, ok := m[n]; ok {
			return true
		}
	}
	return false
}

golang 解法, 执行用时: 16 ms, 内存消耗: 6.4 MB, 提交时间: 2023-10-21 22:38:25

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func twoSumBSTs(root1 *TreeNode, root2 *TreeNode, target int) bool {
	if root1 == nil  {
		return false
	}
	return find(root2, target-root1.Val) ||  twoSumBSTs(root1.Left, root2, target) ||
		twoSumBSTs(root1.Right, root2, target)
}

func find(root *TreeNode, target int) bool {
	if root == nil {
		return false
	}
	if root.Val == target {
		return true
	}
	if root.Val > target {
		return find(root.Left, target)
	}
	return find(root.Right, target)
}

golang 解法, 执行用时: 16 ms, 内存消耗: 6.6 MB, 提交时间: 2023-10-21 22:38:10

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var treeSet map[int]struct{} = make(map[int]struct{})

func oneBST(root1 *TreeNode) {
	if root1 == nil {
		return
	}
	oneBST(root1.Left)
	treeSet[root1.Val] = struct{}{}
	oneBST(root1.Right)
}

func theOtherBST(root2 *TreeNode, target int) bool {
	if root2 == nil {
		return false
	}
	if !theOtherBST(root2.Left, target) {
		if _, ok := treeSet[target - root2.Val]; ok {
			return true
		}
		return theOtherBST(root2.Right, target)
	}
	return true
}

func twoSumBSTs(root1 *TreeNode, root2 *TreeNode, target int) bool {
	treeSet = make(map[int]struct{})
	oneBST(root1)
	if !theOtherBST(root2, target) {
		treeSet = make(map[int]struct{})
		oneBST(root2)
		return theOtherBST(root1, target)
	}
	return true
}

python3 解法, 执行用时: 68 ms, 内存消耗: 22.7 MB, 提交时间: 2023-10-21 22:37:37

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def twoSumBSTs(self, root1: TreeNode, root2: TreeNode, target: int) -> bool:
        a, b = [], []
        self.dfs_LNR(root1, a)
        self.dfs_LNR(root2, b)
        an, bn = len(a), len(b)
        ######## 贪心，双指针，从两边向中间夹逼
        i = 0
        j = bn -1 
        while i < an and 0 <= j:
            if a[i] + b[j] == target:
                return True
            elif a[i] + b[j] < target:
                i += 1
            else:
                j -= 1  
        return False
    ############ 二叉树 中序遍历 ############
    def dfs_LNR(self, rt: TreeNode, res: List[int]) -> None:
        if rt == None:
            return
        self.dfs_LNR(rt.left, res)
        res.append(rt.val)
        self.dfs_LNR(rt.right, res)

cpp 解法, 执行用时: 24 ms, 内存消耗: 28.5 MB, 提交时间: 2023-10-21 22:37:20

/**
 * 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 twoSumBSTs(TreeNode* root1, TreeNode* root2, int target) {
        vector<int> a, b;
        dfs_LNR(root1, a);
        dfs_LNR(root2, b);
        int an = a.size(),  bn = b.size();
        //////// 贪心，双指针，从两边向中间夹逼
        int i = 0;
        int j = bn - 1;
        while (i < an && 0 <= j) {
            if (a[i] + b[j] == target)
                return true;
            else if (a[i] + b[j] < target)
                i ++;
            else
                j --;
        }
        return false;
    }
    //////////// 二叉树，中序遍历 ////////////
    void dfs_LNR(TreeNode * rt, vector<int> & res) {
        if (rt == NULL)
            return ;
        dfs_LNR(rt->left, res);
        res.push_back(rt->val);
        dfs_LNR(rt->right, res);
    }

};

cpp 解法, 执行用时: 28 ms, 内存消耗: 28.8 MB, 提交时间: 2023-10-21 22:35:16

/**
 * 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 {
private:
    vector<int> tree1;
    vector<int> tree2;

    void store(TreeNode * root, vector<int> & tree)
    {
        if(root == nullptr) return;
        store(root->left, tree);
        tree.push_back(root->val);
        store(root->right, tree);
        return;
    }
public:
    bool twoSumBSTs(TreeNode* root1, TreeNode* root2, int target) {
        store(root1, tree1);
        store(root2, tree2);
        int i = 0;
        int j = tree2.size()-1;
        while(i < tree1.size() && j >=0) {
            int curr = tree1[i] + tree2[j];
            if(curr == target)
                return true;
            if(curr < target) {
                i++;
            } else {
                j--;
            }
        }
        return false;
    }
};

java 解法, 执行用时: 1 ms, 内存消耗: 42.7 MB, 提交时间: 2023-10-21 22:34:48

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private boolean find(TreeNode root, int value) {
        if (root == null) {
            return false;
        }
    
        if (root.val == value) {
            return true;
        } else if (root.val < value) {
            return find(root.right, value);
        } else {
            return find(root.left, value);
        }
    }
    
    public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) {
        if (root1 == null) {
            return false;
        }
    
        // 使用或运算进行短路操作，找到就终止
        return find(root2, target - root1.val) || twoSumBSTs(root1.left, root2, target) ||
                twoSumBSTs(root1.right, root2, target);
    }
}

上一题

下一题

详情