617. 合并二叉树
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
示例 1:
输入: Tree 1 Tree 2 1 2 / \ / \ 3 2 1 3 / \ \ 5 4 7 输出: 合并后的树: 3 / \ 4 5 / \ \ 5 4 7
注意: 合并必须从两个树的根节点开始。
方法1–递归
其思路和递归二叉树差不多,只不过我们在递归时多了个相同位置节点的合并.
图解如下:
递归三部曲:
参数和返回值:参数为待合并的两棵树的根节点.返回值为合并后的树根节点.
结束条件:当root1或者root2其中一棵树为空时,直接返回另一个数,并结束递归.
确定单层递归逻辑:当root1和root2都不为空时,先进行跟根节点的合并,之后进行左子树的合并,右子树的合并 (这个题使用先序,中序,后序都可)
注: 我们写的这个代码,主要是把另一棵树root2的值都合并到了root1上,当然我们也可以新建一个树,将节点都合并到新树上.
参考代码1
//方法一 TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) { if(root1==NULL) { return root2; } if(root2==NULL) { return root1; } //修改Tree 1 root1->val +=root2->val;//按照先序进行构造(也可以使用中序和后序) root1->left = mergeTrees(root1->left,root2->left);//构建左子树 root1->right = mergeTrees(root1->left,root2->left);//构建右子树 return root1; }
方法二—迭代(层次遍历)
使用层次遍历,需要每次向队列中加入相同位置的两个节点,然后按照层次遍历的顺序后序一起取出进行操作. 如果该位置另一棵树上无节点,则无需加入该队列,直接将该节点放在对应位置.
参考代码2
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) { if(t1==NULL) { return t2; } if(t2==NULL) { return t1; } queue<TreeNode*> Q; Q.push(t1); Q.push(t2); while(!Q.empty()){ TreeNode* node1 = Q.front(); Q.pop(); TreeNode* node2 = Q.front(); Q.pop(); node1->val += node2->val;//两个对应节点的值进行相加 if(node1->left&&node2->left){//如果对应的左右节点不为空,将其放入队列中进行层次遍历 Q.push(node1->left); Q.push(node2->left); } if(node1->right&&node2->right){ Q.push(node1->right); Q.push(node2->right); } if(node1->left==NULL){//如果左子树为空则直接将对应的另一颗左子树树赋值给左子树. node1->left = node2->left; } if(node1->right==NULL){ node1->right = node2->right; } } return t1; }
700. 二叉搜索树中的搜索
给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。
例如，
给定二叉搜索树: 4 / \ 2 7 / \ 1 3 和值: 2 你应该返回如下子树: 2 / \ 1 3
在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 NULL。
方法1—递归
二叉搜索树是一个有序树：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉搜索树
递归三部曲:
参数和返回值:参数为要递归的子树和要判断的值,返回值为递归后返回的结果(成功则返回对应的子树根节点,失败则返回NULL)
结束条件:如果子树为null则说明该二叉树不存在目标值,返回NULL.如果root->val=val则说明查找成功,直接进行返回.
单层递归逻辑:如果val < root->val ,则向左进行递归,如果 val > root->val 则向右子树进行递归.(同一层只能向一个方向进行递归)
参考代码1
TreeNode* searchBST(TreeNode* root, int val) { if(root==NULL||root->val==val){ return root; } if(val<root->val){ return searchBST(root->left, val); } if(val>root->val){ return searchBST(root->right,val); } }
方法2—迭代
在子树根节点不为空时
如果val < root->val,则更新root,向左子树进行寻找.
如果val > root->val,则更新root,向右字数进行寻找.
如果最后子树根节点已经为NULL了,说明已经寻找到树的尽头了,但是还没有找到val,则直接返回NULL
参考代码2
//迭代法 TreeNode* searchBST(TreeNode* root, int val) { while(root!=NULL){ if(val<root->val){ root = root->left; }else if(val>root->val){ root = root->right; }else{ return root; } } return NULL;//如果没有找到则返回NULL }
98. 验证二叉搜索树
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3] 输出：true
方法一—递归1
按照中序进行递归遍历,判断递归的数组是否是从小到大的顺序,如果是则满足二叉搜索树的特点. 如果不是则不是二叉搜索树.
参考代码1
vector<int> V; void traversal(TreeNode* node) { if(node==NULL) { return; } traversal(node->left); V.push_back(node->val); traversal(node->right); } //思路,按照中序遍历,然后判断形成的数组是否是从小到大的顺序 bool isValidBST(TreeNode* root) { traversal(root); for(int i = 0; i < V.size()-1; i++) { if(V[i]>=V[i+1]) { return false; } } return true; }
方法二—递归2
递归三部曲:
参数和返回值:参数为需要递归的根节点,返回值为该子树是否符合二叉搜索树的特点.
结束条件:当传入的根节点为NULL时,此时子树没有节点,则直接返回true;
单层递归逻辑:先向左进行递归,然后处理中间节点,更新maxVal.最后递归右子树,最后返回左子树,右子树,中间节点的处理结果
参考代码2
long long maxVal = LONG_MIN; //因为后台数据中有int最小值,所以初始化应该为 LONG的最小值. bool isValidBST(TreeNode* root) { if(root==NULL){ return true; } bool left = isValidBST(root->left); //中序遍历验证遍历的元素是否是从小到大 if(maxVal<root->val){ maxVal = root->val; }else{ return false; } bool right = isValidBST(root->right); return left&&right; }
方法三—递归3
上种方法是使用一个全局变量来保存前一个节点,而现在这个方法是使用一个TreeNode 来进行保存.区别不是很大.
参考代码3
TreeNode* pre = NULL; bool isValidBST(TreeNode* root) { if(root==NULL){ return true; } bool left = isValidBST(root->left); //中序遍历验证遍历的元素是否是从小到大 if(pre!=NULL&&pre->val>=root->val){ return false; } pre = root; bool right = isValidBST(root->right); return left&&right; }
