leetcode101. Symmetric Tree

IntMain 發布于2019-08-15 10:58 / 1300人閱讀

摘要：題目要求檢查一棵樹是否是左右對稱的。遞歸在這里遞歸的一般情況是，輸入進行比較的左子樹和右子樹的根節點，先判斷該倆根節點是否等價，然后判斷子節點是否等價。棧通過棧的形式同樣可以實現比較。將需要進行比較的節點依次壓入棧中。

題目要求

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / 
  2   2
 /  / 
3  4 4  3
But the following [1,2,2,null,3,null,3] is not:
    1
   / 
  2   2
      
   3    3
Note:
Bonus points if you could solve it both recursively and iteratively.

檢查一棵樹是否是左右對稱的。

遞歸

在這里遞歸的一般情況是，輸入進行比較的左子樹和右子樹的根節點，先判斷該倆根節點是否等價，然后判斷子節點是否等價。

    public boolean isSymmetric(TreeNode treeNode){
        if(treeNode==null) return true;
        return isSymmetric(treeNode.left, treeNode.right);
    }
    
    public boolean isSymmetric(TreeNode left, TreeNode right){
        if(left==null && right==null) return true;
        if(left!=null && right!=null && left.val==right.val){
            return isSymmetric(left.left, right.right)&&isSymmetric(left.right, right.left);
        }
        return false;
    }

棧

通過棧的形式同樣可以實現比較。將需要進行比較的節點依次壓入棧中。每次從棧中取出兩個進行比較的節點比較。有點像level traversal的思路。

    public boolean isSymmetric2(TreeNode treeNode){
        if(treeNode==null) return true;
        LinkedList stack = new LinkedList();
        TreeNode left = treeNode.left, right = treeNode.right;
        stack.push(left);
        stack.push(right);
        while(!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();
            if(right==null && left==null)continue;
            else if(left==null || right==null)return false;
            else if(left.val==right.val){
                stack.push(left.left);
                stack.push(right.right);
                stack.push(left.right);
                stack.push(right.left);
            }else{
                return false;
            }
        }
        return true;
    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

云服務器 GPU云服務器 Symmetric 101 Leetcod LeetCode

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

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/67455.html

leetcode-101-Symmetric Tree-二叉樹對稱問題

摘要：解題思路所謂的對稱，是左右相反位置的節點的值判斷是否相同。只要出現不同，即可返回即可，否則繼續進行處理。 topic: 101. Symmetric Tree Description: Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For...

seanlook 2019-07-31 11:08 評論0 收藏0
leetcode部分題目答案之JavaScript版

摘要：自己沒事刷的一些的題目，若有更好的解法，希望能夠一起探討項目地址自己沒事刷的一些LeetCode的題目，若有更好的解法，希望能夠一起探討 Number Problem Solution Difficulty 204 Count Primes JavaScript Easy 202 Happy Number JavaScript Easy 190 Reverse Bi...

alphahans 2019-08-21 16:20 評論0 收藏0
[LeetCode] Symmetric Tree

Problem Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). Example For example, this binary tree [1,2,2,3,4,4,3] is symmetric: 1 / 2 2 / / 3 ...

wfc_666 2019-08-15 15:47 評論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
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