leetcode100 Same Tree 引發的對遍歷?算法的思考

cyrils 發布于2019-08-14 17:52 / 3483人閱讀

摘要：判斷兩棵樹是否是相同題目要求傳入兩棵樹的根節點，判斷這兩棵樹是否相同此題的核心就在于如何遍歷樹。定義樹的一種自然方式是遞歸的方式。一棵樹是一些節點的集合，這個集合可以是空集。這個遍歷算法可以用于場景如，計算一個節點的高度。

判斷兩棵樹是否是相同

題目要求：傳入兩棵樹的根節點，判斷這兩棵樹是否相同
此題的核心就在于如何遍歷樹。一旦我們解決了這個問題，題目也就迎刃而解了。
下面就來介紹一下關于樹的一些基本知識

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 引發了

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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