# LeetCode 解題筆記 (Tree類型題目)

解題時要注意的重點
1. 一題多解，找不同的思維；可以看討論區的解題方法
2. 不要盲目刷題，至少要帶走一些想法
3. 精通一種解法；某些題型適合某一種演算法，可以做統整
4. 定義題目內容與輸出的結果；例如考官到底要什麼；題目給的例子是不是分類過的array

[影片來源](https://www.youtube.com/watch?v=NdWYxz3izH4)

## [難度Easy] 類型：Tree
### 100. Same Tree
[題目網址](https://leetcode.com/problems/same-tree)
> 提供一個建構子，該建構子會製造名為left、right的節點跟本身的值，請判斷提供的兩個節點p、q是不是同一個節點
>

#### 解法1

var isSameTree = function(p, q) {
    if(!p && !q) return true
    if(!p || !q || p.val !== q.val) return false
    return isSameTree(p.left,q.left) && isSameTree(p.right,q.right) 
};

看起來很像需要無窮迴圈的檢查，沒有什麼頭緒，想了一陣子想不出來所以找了[別人的解法](https://leetcode.com/problems/same-tree/discuss/32935/JavaScript-solution)；概念是如果沒有p跟q，那代表兩者相同，接著如果沒有p或q或兩者的值不同，那代表不相同，接著回傳該函式去檢查左右node

#### 解法2

var isSameTree = function(p, q) {
  if(p===null) return q===null;
  if(q===null) return p===null;
  if(p.val!==q.val) return false;
  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

概念同上，但比較好理解
[來源](https://leetcode.com/problems/same-tree/discuss/32882/4-lines-javascript)
[另一種類似解法](https://skyyen999.gitbooks.io/-leetcode-with-javascript/content/questions/100md.html)

### 101. Symmetric Tree
[題目網址](https://leetcode.com/problems/symmetric-tree/)
> 提供一個建構子，該建構子會製造名為left、right的節點跟本身的值，請判斷提供的節點是不是呈現對稱排列
>

#### 方法1

var isSymmetric = function(root) {    
    if(!root) return true
    return isLeftRightAreSame(root.right,root.left)
};

function isLeftRightAreSame(r,l){
    if(!r && !l) return true
    if(!r || !l || r.val !== l.val) return false
    
    return isLeftRightAreSame(l.right,r.left) &&
           isLeftRightAreSame(l.left,r.right)
}

概念同 100.Same Tree，都是要把節點放入迴圈內檢查

#### 方法2

var isSymmetric = function(root) {    
    if(!root) return true
    const right = [root.right], left = [root.left]
    while(right.length && left.length){
        const i = right.pop(), j = left.pop()
        if(!i && !j) continue
        if(!i || !j || i.val !== j.val) return false
        right.push(i.left,i.right)
        left.push(j.right,j.left)  
    }
    return true
};

把左右節點放到right、left陣列中，接著拿出來檢查，檢查完之後，把相對應要檢查的節點依照順序放入，如果檢查完都沒出錯，那就是對稱的節點。
[想法來源](https://leetcode.com/problems/symmetric-tree/discuss/33073/JavaScript-recursive-and-iterative-solutions)

#### 方法3

var isSymmetric = function(root) {
    if(root == null || (root.right == null && root.left == null) ){
        return true;
    }

    // 先將right反轉，再比對是否相等
    root.right = revertTree(root.right);
    return isSameTree(root.left,root.right);

    // 反轉樹
    function revertTree(node){
        if(node == null || node.left == null && node.right == null){
            return node;
        }
        var temp = revertTree(node.left);
        node.left = revertTree(node.right);
        node.right = temp;
        return node;
    }


    // 比對是否相等
    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)
    }
};

把節點內容翻轉過來，再檢查是不是相同
[來源](https://skyyen999.gitbooks.io/-leetcode-with-javascript/content/questions/101md.html)

### 104. Maximum Depth of Binary Tree
[題目網址](https://leetcode.com/problems/maximum-depth-of-binary-tree/)
> 提供一個建構子，該建構子會製造名為left、right的節點跟本身的值，請判斷提供的節點最大長度

#### 方法1

var maxDepth = function(root) {
   return root ? 1 + Math.max(maxDepth(root.right),maxDepth(root.left)) : 0
};

如果沒有root結點，回傳0，有的話，至少有1，接著找左右節點最大長度，這邊要使用迭代的方式來尋找

#### 方法2

var maxDepth = function(root) {
   return find(root)
};

function find(n){
   if(!n) return 0 
   let right = 1, left = 1
   if(n.right) right += find(n.right)
   if(n.left) left += find(n.left) 
   return Math.max(right,left) 
}

同方法1，首先有root，那節點就為1，接著宣告right,left總共的節點數量為1，如果能繼續找到節點就加上去，最後看左右哪邊比較大
[來源](https://skyyen999.gitbooks.io/-leetcode-with-javascript/content/questions/104md.html)

###### tags: `LeetCode` `Tree` `easy`