主題

[LeetCode C#] 101. Symmetric Tree - Binary tree, Depth-First Search

帥氣跳蚤蛋 | 2021-07-20 23:14:58 | 巴幣 2 | 人氣 106

難度: Easy
===========================================================================
說明:
給予二元樹的根節點,檢查是否為對稱的樹
===========================================================================
測資1:
Input: root = [1,2,2,3,4,4,3]
Output: true

測資2:
Input: root = [1,2,2,null,3,null,3]
Output: false
===========================================================================
條件限制:
二元樹的節點數量為1~1000
-100 <= Node.val <= 100
===========================================================================
解題:
此提要判斷樹是否對稱,因此須對二元樹進行遍歷,
將原本的樹,由左右節點分割為兩棵樹,進行比較,
採用深度優先搜索(DFS)與遞迴來搜尋整個樹的數值,判斷是否對稱

public class Solution
{
    public bool IsSymmetric(TreeNode root)  //解法與100. Same Tree
    {
        return (Traversal(root.left, root.right));//由左右節點,切分為兩顆獨立的樹
    }

    public bool Traversal(TreeNode lt, TreeNode rt)
    {
        if(lt==null || rt==null)    //若lt或rt有空值
        {
            if (lt == null && rt == null)   //皆為空值表對稱
                return true;
            else  //只有其中之一有值則不對稱
                return false;
        }
        return (lt.val == rt.val) && Traversal(lt.left, rt.right) && Traversal(lt.right, rt.left);  //檢驗數值對稱 && 左右對稱 && 右左對稱
    }

}

創作回應

相關創作

更多創作