劍指Offer_編程題_對稱的二叉樹-有解無憂

題目描述

請實作一個函式，用來判斷一顆二叉樹是不是對稱的，注意，如果一個二叉樹同此二叉樹的鏡像是同樣的，定義其為對稱的，

鏈接：https://www.nowcoder.com/questionTerminal/ff05d44dfdb04e1d83bdbdab320efbcb?f=discussion
來源：牛客網

//===================遞回演算法=============================// 1.只要pRoot.left和pRoot.right是否對稱即可 2.左右節點的值相等且對稱子樹left.left， right.right ;left.rigth,right.left也對稱

鏈接：https://www.nowcoder.com/questionTerminal/ff05d44dfdb04e1d83bdbdab320efbcb?f=discussion
來源：牛客網

 boolean isSymmetrical(TreeNode pRoot)
    {
        if(pRoot == null) return true;
        return isSymmetrical(pRoot.left, pRoot.right);
    }
    private boolean isSymmetrical(TreeNode left, TreeNode right) {
        if(left == null && right == null) return true;
        if(left == null || right == null) return false;
        return left.val == right.val //為鏡像的條件：左右節點值相等
                && isSymmetrical(left.left, right.right) 
            //2.對稱的子樹也是鏡像
                && isSymmetrical(left.right, right.left);
    }

鏈接：https://www.nowcoder.com/questionTerminal/ff05d44dfdb04e1d83bdbdab320efbcb?f=discussion
來源：牛客網

//===================非遞回演算法，利用DFS和BFS=============================//
/*
* DFS使用stack來保存成對的節點

* 1.出堆疊的時候也是成對成對的， 1.若都為空，繼續； 2.一個為空，回傳false; 3.不為空，比較當前值，值不等，回傳false；

* 2.確定入堆疊順序，每次入堆疊都是成對成對的，如left.left， right.right ;left.rigth,right.left
*/

鏈接：https://www.nowcoder.com/questionTerminal/ff05d44dfdb04e1d83bdbdab320efbcb?f=discussion
來源：牛客網

boolean isSymmetricalDFS(TreeNode pRoot)
    {
        if(pRoot == null) return true;
        Stack<TreeNode> s = new Stack<>();
        s.push(pRoot.left);
        s.push(pRoot.right);
        while(!s.empty()) {
            TreeNode right = s.pop();//成對取出
            TreeNode left = s.pop();
            if(left == null && right == null) continue;
            if(left == null || right == null) return false;
            if(left.val != right.val) return false;
            //成對插入
            s.push(left.left);
            s.push(right.right);
            s.push(left.right);
            s.push(right.left);
        }
        return true;
    }

鏈接：https://www.nowcoder.com/questionTerminal/ff05d44dfdb04e1d83bdbdab320efbcb?f=discussion
來源：牛客網

/*
* BFS使用Queue來保存成對的節點，代碼和上面極其相似

* 1.出隊的時候也是成對成對的 1.若都為空，繼續； 2.一個為空，回傳false; 3.不為空，比較當前值，值不等，回傳false；

* 2.確定入隊順序，每次入隊都是成對成對的，如left.left， right.right ;left.rigth,right.left
*/

鏈接：https://www.nowcoder.com/questionTerminal/ff05d44dfdb04e1d83bdbdab320efbcb?f=discussion
來源：牛客網

boolean isSymmetricalBFS(TreeNode pRoot)
    {
        if(pRoot == null) return true;
        Queue<TreeNode> s = new LinkedList<>();
        s.offer(pRoot.left);
        s.offer(pRoot.right);
        while(!s.isEmpty()) {
            TreeNode left= s.poll();//成對取出
            TreeNode right= s.poll();
            if(left == null && right == null) continue;
            if(left == null || right == null) return false;
            if(left.val != right.val) return false;
            //成對插入
            s.offer(left.left);
            s.offer(right.right);
            s.offer(left.right);
            s.offer(right.left);
        }
        return true;
    }

解題相關答案：

https://www.nowcoder.com/questionTerminal/ff05d44dfdb04e1d83bdbdab320efbcb?f=discussion

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/185734.html

標籤：Java

上一篇：Docker中使用ElasticSearch

下一篇：LeetCode 160. 相交鏈表