leetcode100 Same Tree 引發(fā)的對(duì)遍歷?算法的思考

cyrils 發(fā)布于2019-08-14 17:52 / 3480人閱讀

摘要：判斷兩棵樹(shù)是否是相同題目要求傳入兩棵樹(shù)的根節(jié)點(diǎn)，判斷這兩棵樹(shù)是否相同此題的核心就在于如何遍歷樹(shù)。定義樹(shù)的一種自然方式是遞歸的方式。一棵樹(shù)是一些節(jié)點(diǎn)的集合，這個(gè)集合可以是空集。這個(gè)遍歷算法可以用于場(chǎng)景如，計(jì)算一個(gè)節(jié)點(diǎn)的高度。

判斷兩棵樹(shù)是否是相同

題目要求：傳入兩棵樹(shù)的根節(jié)點(diǎn)，判斷這兩棵樹(shù)是否相同
此題的核心就在于如何遍歷樹(shù)。一旦我們解決了這個(gè)問(wèn)題，題目也就迎刃而解了。
下面就來(lái)介紹一下關(guān)于樹(shù)的一些基本知識(shí)

1.預(yù)備知識(shí)

樹(shù)（tree）可以用幾種方式定義。定義樹(shù)的一種自然方式是遞歸的方式。一棵樹(shù)是一些節(jié)點(diǎn)的集合，這個(gè)集合可以是空集。若不是空集，則樹(shù)由叫做根（root）的節(jié)點(diǎn)r以及0個(gè)或多個(gè)非空子樹(shù)T1，T2...Tk組成，這些子樹(shù)中每一棵的根都被來(lái)自根r的一條有向的邊（edge）所連結(jié)。

節(jié)點(diǎn)的深度：從根到該節(jié)點(diǎn)的唯一的路徑的長(zhǎng)

二叉樹(shù)：一個(gè)每個(gè)節(jié)點(diǎn)都不能有多于兩個(gè)兒子的樹(shù)
題目中二叉樹(shù)的節(jié)點(diǎn)表示為

   class TreeNode{
        //節(jié)點(diǎn)的值
        int val;
        //左子節(jié)點(diǎn)，可以為null
        TreeNode left;
        //右子節(jié)點(diǎn)，可以為null
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

2.二叉樹(shù)的遍歷方法

中序遍歷：首先處理左子樹(shù)，然后是當(dāng)前節(jié)點(diǎn)，最后處理右子樹(shù)。這個(gè)算法的總的運(yùn)行時(shí)間是O(N)，這是因?yàn)樵跇?shù)的每一個(gè)節(jié)點(diǎn)處進(jìn)行的工作是常數(shù)時(shí)間，一共有n個(gè)節(jié)點(diǎn)，所以運(yùn)行時(shí)間為O(N)

后序遍歷：先處理左子樹(shù)，再處理右子樹(shù)，然后再處理當(dāng)前節(jié)點(diǎn)。這個(gè)遍歷算法可以用于場(chǎng)景如，計(jì)算一個(gè)節(jié)點(diǎn)的高度。

先序遍歷：先處理當(dāng)前節(jié)點(diǎn)，在處理左子樹(shù)和右子樹(shù)

層序遍歷：所有深度為d的節(jié)點(diǎn)要在深度d+1的節(jié)點(diǎn)之前重組

    //二叉樹(shù)的中序遍歷 
    //遞歸
    void inOrder(TreeNode node){
        if(node!=null){
            inOrder(node.left);
            visit(node);
            inOrder(node.right);
        }
    }
    
    //二叉樹(shù)的中序遍歷
    //非遞歸 需要利用棧
    void inOrder(TreeNode node){
        Stack s = new Stack();
        TreeNode temp = node;
        for( ; ; ){
            //訪問(wèn)左節(jié)點(diǎn)
            while(temp!=null){
                s.push(temp);
                temp = temp.left;
            }
            
            //從左節(jié)點(diǎn)回來(lái)，訪問(wèn)右節(jié)點(diǎn)
            if(!s.isEmpty()){
                temp = s.pop();
                //訪問(wèn)當(dāng)前節(jié)點(diǎn)
                System.out.println(temp.val);
                temp = temp.right;
            }else{
                return;
            }
        }
    }
    //二叉樹(shù)的后序遍歷
    void postOrder(TreeNode node){
        if(node!=null){
            postOrder(node.left);
            postOrder(node.right);
            visit(node);
        }
    }
    
    //二叉樹(shù)的前序遍歷
    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 {

    //遞歸 即當(dāng)前值和左右子樹(shù)都相等，則是相同的樹(shù)，否則不是
    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;
        }
    }
    
    //循環(huán) 中序遍歷
    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; }
    }
}

想要了解更多開(kāi)發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~