leetcode100 Same Tree 引发的对遍历?算法的思考

cyrils 发布于2019-08-14 17:52 / 3541人阅读

摘要：判断两棵树是否是相同题目要求传入两棵树的根节点，判断这两棵树是否相同此题的核心就在于如何遍历树。定义树的一种自然方式是递归的方式。一棵树是一些节点的集合，这个集合可以是空集。这个遍历算法可以用于场景如，计算一个节点的高度。

判断两棵树是否是相同

题目要求：传入两棵树的根节点，判断这两棵树是否相同
此题的核心就在于如何遍历树。一旦我们解决了这个问题，题目也就迎刃而解了。
下面就来介绍一下关于树的一些基本知识

1.预备知识

树（tree）可以用几种方式定义。定义树的一种自然方式是递归的方式。一棵树是一些节点的集合，这个集合可以是空集。若不是空集，则树由叫做根（root）的节点r以及0个或多个非空子树T1，T2...Tk组成，这些子树中每一棵的根都被来自根r的一条有向的边（edge）所连结。

节点的深度：从根到该节点的唯一的路径的长

二叉树：一个每个节点都不能有多于两个儿子的树
题目中二叉树的节点表示为

</>复制代码 
   class TreeNode{
        //节点的值
        int val;
        //左子节点，可以为null
        TreeNode left;
        //右子节点，可以为null
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

2.二叉树的遍历方法

中序遍历：首先处理左子树，然后是当前节点，最后处理右子树。这个算法的总的运行时间是O(N)，这是因为在树的每一个节点处进行的工作是常数时间，一共有n个节点，所以运行时间为O(N)

后序遍历：先处理左子树，再处理右子树，然后再处理当前节点。这个遍历算法可以用于场景如，计算一个节点的高度。

先序遍历：先处理当前节点，在处理左子树和右子树

层序遍历：所有深度为d的节点要在深度d+1的节点之前重组

</>复制代码 
    //二叉树的中序遍历 
    //递归
    void inOrder(TreeNode node){
        if(node!=null){
            inOrder(node.left);
            visit(node);
            inOrder(node.right);
        }
    }
    
    //二叉树的中序遍历
    //非递归 需要利用栈
    void inOrder(TreeNode node){
        Stack s = new Stack();
        TreeNode temp = node;
        for( ; ; ){
            //访问左节点
            while(temp!=null){
                s.push(temp);
                temp = temp.left;
            }
            
            //从左节点回来，访问右节点
            if(!s.isEmpty()){
                temp = s.pop();
                //访问当前节点
                System.out.println(temp.val);
                temp = temp.right;
            }else{
                return;
            }
        }
    }
    //二叉树的后序遍历
    void postOrder(TreeNode node){
        if(node!=null){
            postOrder(node.left);
            postOrder(node.right);
            visit(node);
        }
    }
    
    //二叉树的前序遍历
    void preOrder(TreeNode node){
        if(node!=null){
            visit(node);
            preOrder(node.left);
            preOrder(node.right);
        }
    }

3.本题的解法

</>复制代码 
**
 * @author rale
 * leetcode100
 * Given two binary trees, write a function to check if they are equal or not.
 * Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
 */
public class SameTree {
    //递归 即当前值和左右子树都相等，则是相同的树，否则不是
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null){
            return q==null?true:false;
        }else if(q==null){
            return p==null?true:false;
        }
        if(p.val == q.val){
            return isSameTree(p.left,q.left)&&isSameTree(p.right, q.right);
        }else{
            return false;
        }
    }
    
    //循环 中序遍历
    public boolean isSameTree2(TreeNode p, TreeNode q){
        Stack stackP = new Stack();
        Stack stackQ = new Stack();
        if(p!=null){
            stackP.push(p);
        }
        if(q!=null){
            stackQ.push(q);
        }
        while(!stackP.isEmpty() && !stackQ.isEmpty()){
            TreeNode tempP = stackP.pop();
            TreeNode tempQ = stackQ.pop();
            if(tempP.val!=tempQ.val){
                return false;
            }
            if(tempP.right!=null){
                stackP.push(tempP.right);
            }
            if(tempQ.right!=null){
                stackQ.push(tempQ.right);
            }
            if(stackP.size()!=stackQ.size()){
                return false;
            }
            if(tempP.left!=null){
                stackP.push(tempP.left);
            }
            if(tempQ.left!=null){
                stackQ.push(tempQ.left);
            }
            if(stackP.size()!=stackQ.size()){
                return false;
            }
        }
        return stackP.size()==stackQ.size();
    }
    
    public class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

GPU云服务器云服务器人工智能的思考对人工智能的思考 Same 引发了

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66848.html

LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月汇总（55 题攻略）

摘要：微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目录不...

warmcheng 2019-08-26 10:09 评论0 收藏0
leetcode297. Serialize and Deserialize Binary Tree

摘要：因此题目中的例子的中序遍历结果为。但是，标准的中序遍历并不能使我们将该结果反构造成一棵树，我们丢失了父节点和子节点之间的关系。这里我们也可以明显的看出来，中序遍历需要保存的空值远远多于广度优先遍历。题目要求 Serialization is the process of converting a data structure or object into a sequence of ...

desdik 2019-08-15 14:30 评论0 收藏0
[Leetcode] Same Tree Symmetric Tree 相同树对称树

摘要：递归法复杂度时间空间递归栈空间思路如果两个根节点一个为空，一个不为空，或者两个根节点值不同，说明出现了不一样的地方，返回假。代码递归法复杂度时间空间递归栈空间思路其实和写法是一样的，是比较两个节点的两个左边，然后再比较两个节点的两个右边。 Same Tree Given two binary trees, write a function to check if they are eq...

TZLLOG 2019-08-14 12:32 评论0 收藏0
leetcode449. Serialize and Deserialize BST

摘要：题目要求将二叉搜索树序列化和反序列化，序列化是指将树用字符串的形式表示，反序列化是指将字符串形式的树还原成原来的样子。假如二叉搜索树的节点较多，该算法将会占用大量的额外空间。题目要求 Serialization is the process of converting a data structure or object into a sequence of bits so that...

Honwhy 2019-08-16 16:58 评论0 收藏0