leedcode

算法题练习，锻炼一下脑瓜子

常见的数据结构

• 数组Array
• 链表
• 二叉树（每个节点最多2个子节点的树）

js代码

数组

var a = new Array(1,2,3,4)
// [1,2,3,4]

链表

function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val)
    this.next = (next === undefined ? null : next)
}
var l1 = new ListNode(1, 
            new ListNode(2, 
                new ListNode(3, null)
            )
    )
// {
//     "val": 1,
//     "next": {
//         "val": 2,
//         "next": {
//             "val": 3,
//             "next": null
//         }
//     }
// }

二叉树

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}
var root = new TreeNode(1, new TreeNode(3, 
                                            new TreeNode(5, null, null), 
                                            null), 
                           new TreeNode(2, 
                                            new TreeNode(4, null, null),
                                            null))
// {
//     "val": 1,
//     "left": {
//         "val": 3,
//         "left": {
//             "val": 5,
//             "left": null,
//             "right": null
//         },
//         "right": null
//     },
//     "right": {
//         "val": 2,
//         "left": {
//             "val": 4,
//             "left": null,
//             "right": null
//         },
//         "right": null
//     }
// }

树的特点

• 树的任意2个节点有且仅有一条路径
• 树的节点树为n，那么一定是n-1条路径
• 没有父节点的称为根节点
• 没有子节点的称为叶节点
• 不是根节点和叶节点的称为内部节点
• 二叉树每个节点最多只有2个子节点
• 二叉树的节点有顺序，即分左右，在图上表示为空，但是在代码里一般要用null占位

二叉树的遍历

前序 遍历根节点，遍历左子树，遍历右子树

中序 遍历左子树，遍历根节点，遍历右子树 中序遍历的效果，就像把树垂直投影到地面，树节点的顺序就是遍历的顺序

后序 遍历左子树，遍历右子树，遍历根节点