101. 對稱二叉樹

給定一個二叉樹，檢查它是否是鏡像對稱的。

例如，二叉樹 [1,2,2,3,4,4,3] 是對稱的。

image.png

但是下面這個 [1,2,2,null,3,null,3] 則不是鏡像對稱的:

image.png

說明:

如果你可以運用遞歸和迭代兩種方法解決這個問題，會很加分。

package leetcode

import "zheng/sort"

/*
給定一個二叉樹，檢查它是否是鏡像對稱的。

例如，二叉樹 [1,2,2,3,4,4,3] 是對稱的。

1

/
2 2
/ \ /
3 4 4 3
但是下面這個 [1,2,2,null,3,null,3] 則不是鏡像對稱的:

1

/
2 2
\
3 3

說明:

如果你可以運用遞歸和迭代兩種方法解決這個問題，會很加分。

package leetcode

import "zheng/sort"

/*
給定一個二叉樹，檢查它是否是鏡像對稱的。

例如，二叉樹 [1,2,2,3,4,4,3] 是對稱的。

    1
   / \
  2   2
 / \ / \
3  4 4  3
但是下面這個 [1,2,2,null,3,null,3] 則不是鏡像對稱的:

    1
   / \
  2   2
   \   \
   3    3

說明:

如果你可以運用遞歸和迭代兩種方法解決這個問題，會很加分。
*/

// TreeNode Definition for a binary tree node.
// type TreeNode struct {
//  Val   int
//  Left  *TreeNode
//  Right *TreeNode
// }

// 思路：根結(jié)點的左子樹按照根->左->右的方式遍歷，根結(jié)點的右子樹按照根->右->左的方式遍歷，
func isSymmetric(root *TreeNode) bool {

    if root == nil {
        return true
    }
    leftNode := root.Left
    rightNode := root.Right

    if leftNode == nil && rightNode == nil {
        return true
    }

    leftList := preOrderLeftNode(leftNode)
    rightList := preOrderRightNode(rightNode)

    if len(leftList) != len(rightList) {
        return false
    }
    for i := 0; i < len(leftList); i++ {
        if leftList[i] != rightList[i] {
            return false
        }
    }
    return true
}

func preOrderLeftNode(leftNode *TreeNode) []int {
    leftList := make([]int, 0)
    stack := sort.NewStack()

    if leftNode == nil {
        return leftList
    }
    for {
        leftList = append(leftList, leftNode.Val)
        if leftNode.Right != nil {
            stack.Push(leftNode.Right)
        }
        if leftNode.Left != nil {
            leftNode = leftNode.Left
        } else {
            leftList = append(leftList, -1)

            if stack.Len() != 0 {
                leftNode = stack.Pop().(*TreeNode)
            } else {
                leftNode = nil
            }
        }
        if leftNode == nil {
            break
        }
    }
    return leftList
}

func preOrderRightNode(rightNode *TreeNode) []int {
    rightList := make([]int, 0)
    stack := sort.NewStack()

    if rightNode == nil {
        return rightList
    }

    for {
        rightList = append(rightList, rightNode.Val)
        if rightNode.Left != nil {
            stack.Push(rightNode.Left)
        }
        if rightNode.Right != nil {
            rightNode = rightNode.Right

        } else {

            rightList = append(rightList, -1)
            if stack.Len() != 0 {
                rightNode = stack.Pop().(*TreeNode)
            } else {
                rightNode = nil
            }
        }
        if rightNode == nil {
            break
        }
    }
    return rightList
}

package sort

import "container/list"

type Stack struct {
    list *list.List
}

func NewStack() *Stack {
    list := list.New()
    return &Stack{list}
}

func (stack *Stack) Push(value interface{}) {
    stack.list.PushBack(value)
}

func (stack *Stack) Pop() interface{} {
    e := stack.list.Back()
    if e != nil {
        stack.list.Remove(e)
        return e.Value
    }
    return nil
}

func (stack *Stack) Peak() interface{} {
    e := stack.list.Back()
    if e != nil {
        return e.Value
    }

    return nil
}

func (stack *Stack) Len() int {
    return stack.list.Len()
}

func (stack *Stack) Empty() bool {
    return stack.list.Len() == 0
}