二叉树的递归遍历
特点1 虽然是从root开始，但是 严重依赖从下到上的反馈的数据 ，例如求tree的高度
题目1 最近公共祖先（LCA）
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
2和5
8和7
image.png
code
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root ==NULL)
{
return root;
}
if(root ==p || root ==q)
{
return root;
}
TreeNode* left =lowestCommonAncestor(root->left,p,q);
TreeNode* right=lowestCommonAncestor(root->right,p,q);
if(left && right)
{
return root;
}
return left ?left:right;
}
};题目2 LeetCode 110. Balanced Binary Tree
依赖下面反馈
合并在一起
特点2 从上到下，依赖当前root节点判断
1 翻转等价二叉树
我们可以为二叉树 T 定义一个翻转操作，如下所示：选择任意节点，然后交换它的左子树和右子树。 只要经过一定次数的翻转操作后，能使 X 等于 Y，我们就称二叉树 X 翻转等价于二叉树 Y。 编写一个判断两个二叉树是否是翻转等价的函数。这些树由根节点 root1 和 root2 给出
- 选择任意节点，然后交换它的左子树和右子树
- 左子树和右子树是否继续交换呢？ 是否选择了任意节点？ 等价tree和翻转等级tree的结合
测试
题目理解错误，以为是全部都翻转了
code
执行用时 : 12 ms
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool flipEquiv(TreeNode* root1, TreeNode* root2) {
if(root1 ==NULL && root2 ==NULL)
{
return true;
}
if((root1!=NULL && root2==NULL) ||(root2!=NULL &&root1==NULL)||root1->val !=root2->val)
{
return false;
}
/**
if(root1->left !=root2->right ||root1->right !=root2->left)
{
return false;
}**/
return flipEquiv(root1->left,root2->right) && flipEquiv(root1->right,root2->left) || flipEquiv(root1->left,root2->left) && flipEquiv(root1->right,root2->right);
}
};
func flipEquiv(root1, root2 *TreeNode) bool {
if root1 == nil && root2 == nil {
return true
}
if (root1 != nil && root2 == nil) ||
(root1 == nil && root2 != nil) ||
root1.Val != root2.Val {
return false
}
if (flipEquiv(root1.Left, root2.Left) && flipEquiv(root1.Right, root2.Right)) ||
(flipEquiv(root1.Left, root2.Right) && flipEquiv(root1.Right, root2.Left)) {
return true
}
return false
}2 Leetcode 226： 翻转二叉树
翻转一棵二叉树
- root保持不变
- 左右子树交换
- 重复步骤1和2
测试
翻转一棵二叉树
code
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root == NULL)
{
return root;
}
//!!!!!
TreeNode *temp=root->left;
root->left =root->right;
root->right=temp;
invertTree(root->left);
invertTree(root->right);
return root;
}
};本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-04-07，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
