专栏首页架构说二叉树的递归遍历

二叉树的递归遍历

特点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;
    }
};

本文分享自微信公众号 - 架构说(JiaGouS),作者:王传义

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-04-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 漫谈递归-链表合并

    将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

    程序员小王
  • 958. 二叉树的完全性检验

    输入:[1,2,3,4,5,null,7] 输出:false 解释:值为 7 的结点没有尽可能靠向左侧

    程序员小王
  • 单链表中头节点作用(深入理解)

    今天QQ群里有人咨询一个问题 例如单链表中头节点作用 然后联想到做项目中解决core一个问题 虽然每天都在吃饭睡觉打豆豆,啥框架业务都不懂 解决了这一个...

    程序员小王
  • PWA - 令人惊奇的web用户体验新方法

    install 事件回调中有两个方法: * event.waitUntil():传入一个 Promise 为参数,等到该 Promise 为 resolve 状...

    江米小枣
  • 卷积神经网络学习路线(三)| 盘点不同类型的池化层、1*1卷积的作用和卷积核是否一定越大越好?

    这是卷积神经网络学习路线的第三篇,这一篇开始盘点一下池化层的不同类型和1*1卷积的作用。

    BBuf
  • 卷积神经网络(CNN)

            CNN,即卷积神经网络,主要用于图像识别,分类。这篇卷积神经网络是前面介绍的多层神经网络的进一步深入,它将深度学习的思想引入到了神经网络当中,通...

    Flaneur
  • 卷积操作转化成矩阵乘法

    平常都是无脑使用Pytorch提供的nn.Conv2d方法,但是并不关心具体该如何实现,原来是把卷积操作转化成矩阵乘法,而不是真的通过滑动卷积核来做卷积,下面做...

    marsggbo
  • InceptionV3 网络模型

    GoogLeNet inceptionV1 到 V4,一直都在逐步改进,本文主要是阅读 V3 的论文学习总结。

    琦在江湖飘
  • 深度学习论文笔记(六)--- FCN-2015年(Fully Convolutional Networks for Semantic Segmentation)

    深度学习论文笔记(六)--- FCN 全连接网络 FullyConvolutional Networks for Semantic Segmentation ...

    TeeyoHuang
  • 一些常被忽略又很有用的小技巧

    手画肯定不可能了,但以为要安装什么小工具才能拧出来。结果是一两行命令的事情。 window系统:打开cmd.exe界面,输入如下指令:

    celineWong7

扫码关注云+社区

领取腾讯云代金券