[IT技術30篇挑戰] 資料結構和演算法實作 DAY12 – 遞迴與迭代解 @地瓜大的飛翔旅程

章節連結

遞迴和迭代

遞迴
迭代

LeetCode 練習記錄
系列文章

遞迴和迭代這兩個概念，在任何的程式語言中，都是非常常用的工具，可以簡化你的程式碼並更有邏輯性。

遞迴和迭代

無論是採用何種方法，在開始前，請先注意有無特殊解(邊界條件)或是可以化簡的東西。

遞迴

反覆呼叫本身函式，然後得到最後的答案。過程中，會形成 Stack 的結構來儲存中途所產生的資料，會有上線的問題。

迭代

透過迴圈來取代”遞迴呼叫自己”，進而得到解答

LeetCode 練習記錄

// 101. Symmetric Tree
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    /*start from root*/
    if(root === null || (root.right === null && root.left === null)){
        return true
    }
    
    /*revertTree*/
    function revertTree(node){
        if(node === null || (node.left === null && node.right === null)){
            return node
        }
        let temp = revertTree(node.left)
        node.left = revertTree(node.right)
        node.right = temp
        return node
    }
    
    /*compare isSame?*/
    function isSameTree(left,right){
        if(left === null && right === null){
            return true
        }
        if((left === null && right !== null) ||(right === null && left !== null)){
            return false
        }
        if(left.val !== right.val){
            return false
        }
        return isSameTree(left.right,right.right) && isSameTree(left.left,right.left)
    }
    
    
    /*revert right tree to left and compare them whether they are the same.*/
    root.right = revertTree(root.right)
    return isSameTree(root.left,root.right)
};