文档章节

Same Tree

哭哭吓唬你
 哭哭吓唬你
发布于 2014/07/31 12:51
字数 230
阅读 3
收藏 0

该题目用来解决两棵二叉树是否是同一颗树!解决的方式是通过树的遍历来判断两棵树的节点是否是相等。

考虑到效率问题,该题目使用前序遍历比较好。比较不相等可以立即返回。

1. 采用非递归方式遍历树。

public boolean isSameTree(TreeNode p, TreeNode q) {
        Stack<TreeNode> first = new Stack<TreeNode>();
        Stack<TreeNode> second = new Stack<TreeNode>();
        TreeNode fP = p;
        TreeNode sQ = q;
        while((fP!=null || !first.isEmpty()) && (sQ!=null || !second.isEmpty())){
        	
        	if(fP==null || sQ == null){
        		return fP == sQ;
        	}
        	while(fP!=null && sQ!=null){
        		if(fP.val != sQ.val){
        			return false;
        		}
        		
        		first.push(fP);
        		second.push(sQ);
        		fP = fP.left;
        		sQ = sQ.left;
        	}
        	
        	if(!first.isEmpty() && !second.isEmpty()){
        		fP = first.pop();
        		sQ = second.pop();
        		fP = fP.right;
        		sQ = sQ.right;
        	}
        }
        
        if(!first.isEmpty() || !second.isEmpty()){
        	return false;
        }
        return true;
    }



2. 使用递归方式遍历。

  public boolean isSameTree(TreeNode p, TreeNode q) {
     if(p == null || q == null){
         return p == q;
     }
     
     return (p.val == q.val) && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
   }



© 著作权归作者所有

上一篇: Reverse Integer
下一篇: Single Number
哭哭吓唬你
粉丝 4
博文 102
码字总数 40621
作品 0
石景山
程序员
私信 提问
树的非递归遍历

//定义树结构 struct Tree{ int data; Tree *left; Tree *right; Tree(){ this->data = 0; this->left = nullptr; this->right = nullptr; } }; //递归先序遍历 void visit_recursive1(Tree......

yizhangxyz
2016/11/03
14
0
python 数据结构 tree 的插入和遍历

coding:utf-8 class Node(object): """docstring for Node""" def init(self, item=-1, lchild=None, rchild=None): self.item = item self.lchild = lchild self.rchild = rchild class Tre......

hyhlinux
2016/11/17
43
0
Redhat 64 位下 安装gcc 4.8.2 问题 ,bug困扰我很久了。。

你好,麻烦请教个问题,困扰了我很久了。。 我想在linux Redhat 64 位系统上安装 GCC-4.8.2,出现了如下bug: g++ -c -g -DIN_GCC -fno-exceptions -fno-rtti -fasynchronous-unwind-tables ...

linuxcainiao
2014/03/02
1K
1
诚心请教一个Linux Redhat 64位下GCC 4.8 安装问题 bug 已经困扰我很久了。。。

@ayanamist 你好,想跟你请教个问题: 困扰了我很久了。。 我想在linux Redhat 64 位系统上安装 GCC-4.8.2,出现了如下bug: g++ -c -g -DIN_GCC -fno-exceptions -fno-rtti -fasynchronous-...

linuxcainiao
2014/03/02
1K
3
C++建立二叉树,先建立后打印出问题了

#include #include using namespace std; template struct TreeNode { T data; TreeNode* lchild; TreeNode* rchild; }; template class BinTree { public: BinTree(){root = NULL;}; TreeNo......

来就是玩的
2015/03/06
269
1

没有更多内容

加载失败,请刷新页面

加载更多

查看线上日志常用命令

cat 命令(文本输出命令) 通常查找出错误日志 cat error.log | grep 'nick' , 这时候我们要输出当前这个日志的前后几行: 显示file文件里匹配nick那行以及上下5行 cat error.log | grep -C ...

xiaolyuh
39分钟前
5
0
六、Java设计模式之工厂方法

工厂方法定义: 定义一个创建对象的接口,但让实现这个接口的类来决定实例化哪个类,工厂方法让类的实例化推迟到子类中进行 类型:创建型 工厂方法-使用场景: 创建对象需要大量重复的代码 ...

东风破2019
45分钟前
5
0
win服务器管理遇到的一系列问题记录

有些小伙伴在使用iis7远程桌面管理工具的时候总是会遇到一系列的问题,下面就是为大家介绍一下服务器日常管理过程中出现的问题及我的解决办法和心得。希望能帮到大家。   拒绝服务器重新启...

1717197346
52分钟前
6
0
flutter 剪切板 复制粘贴

复制粘贴功能 import 'package:flutter/services.dart'; Clipboard.setData(ClipboardData(text:_text));Clipboard.getData;...

zdglf
55分钟前
4
0
如何保证消息的可靠性传输?或者说,如何处理消息丢失的问题?

面试题 如何保证消息的可靠性传输?或者说,如何处理消息丢失的问题? 面试官心理分析 这个是肯定的,用 MQ 有个基本原则,就是数据不能多一条,也不能少一条,不能多,就是前面说的重复消费...

米兜
56分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部