算法
二叉树的锯齿形层次遍历
给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如： 给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回锯齿形层次遍历如下：
[
[3],
[20,9],
[15,7]
]
var zigzagLevelOrder = function(root) {
var res = [];
const inorder = (node, len) => {
if(!node) return;
if(!res[len]) res[len] = [];
if(len % 2 === 0){
res[len].push(node.val);
}else{
res[len].unshift(node.val);
}
inorder(node.left, len + 1);
inorder(node.right, len + 1);
}
inorder(root, 0);
return res;
};
点光源
var VSHADER_SOURCE = `
attribute vec4 a_Position;
attribute vec4 a_Color;
attribute vec4 a_Normal;
uniform mat4 u_MvpMatrix;
uniform mat4 u_ModelMatrix;
uniform mat4 u_NormalMatrix;
uniform vec3 u_LightColor;
uniform vec3 u_LightPosition;
uniform vec3 u_AmbientLight;
varying vec4 v_Color;
void main() {
gl_Position = u_MvpMatrix * a_Position;
vec3 normal = normalize(vec3(u_NormalMatrix * a_Normal));
vec4 vertexPosition = u_ModelMatrix * a_Position;
vec3 lightDirection = normalize(u_LightPosition - vec3(vertexPosition));
float nDotL = max(dot(lightDirection, normal), 0.0);
vec3 diffuse = u_LightColor * vec3(a_Color) * nDotL;
vec3 ambient = u_AmbientLight * vec3(a_Color);
v_Color = vec4(diffuse + ambient, a_Color.a);
}
`;
var FSHADER_SOURCE = `
#ifdef GL_ES
precision mediump float;
#endif
varying vec4 v_Color;
void main() {
gl_FragColor = v_Color;
}
`;
var gl = canvas.getContext('webgl');
initShaders(gl, VSHADER_SOURCE, FSHADER_SOURCE)
this.gl = gl;
var n = this.initVertexBuffers(gl)
gl.clearColor(0, 0, 0, 1);
gl.enable(gl.DEPTH_TEST);
var u_ModelMatrix = gl.getUniformLocation(gl.program, 'u_ModelMatrix');
var u_MvpMatrix = gl.getUniformLocation(gl.program, 'u_MvpMatrix');//模型视图投影矩阵
var u_NormalMatrix = gl.getUniformLocation(gl.program, 'u_NormalMatrix');
var u_LightColor = gl.getUniformLocation(gl.program, 'u_LightColor');
var u_LightPosition = gl.getUniformLocation(gl.program, 'u_LightPosition');
var u_AmbientLight = gl.getUniformLocation(gl.program, 'u_AmbientLight');
if (!u_MvpMatrix || !u_NormalMatrix || !u_LightColor || !u_LightPosition || !u_AmbientLight) {
console.log('Failed to get the storage location');
return;
}
gl.uniform3f(u_LightColor, 1.0, 1.0, 1.0); //设置光线颜色为白色
gl.uniform3f(u_LightPosition, 2.3, 4.0, 3.5);//设置光线位置（在世界坐标系下）
gl.uniform3f(u_AmbientLight, 0.2, 0.2, 0.2); //设置环境光颜色
var modelMatrix = new Matrix4(); // Model matrix
var mvpMatrix = new Matrix4(); // Model view projection matrix
var normalMatrix = new Matrix4(); // Transformation matrix for normals
modelMatrix.setRotate(90, 0, 1, 0);
gl.uniformMatrix4fv(u_ModelMatrix, false, modelMatrix.elements);
mvpMatrix.setPerspective(30, canvas.width/canvas.height, 1 ,100);
mvpMatrix.lookAt(6, 6, 14, 0, 0, 0, 0, 1, 0);
mvpMatrix.multiply(modelMatrix);
gl.uniformMatrix4fv(u_MvpMatrix, false, mvpMatrix.elements);
normalMatrix.setInverseOf(modelMatrix);
normalMatrix.transpose();
gl.uniformMatrix4fv(u_NormalMatrix, false, normalMatrix.elements);
gl.clear(gl.COLOR_BUFFER_BIT | gl.DEPTH_BUFFER_BIT);
gl.drawElements(gl.TRIANGLES, n, gl.UNSIGNED_BYTE, 0);
initVertexBuffers(gl){
// Create a cube
// v6----- v5
// /| /|
// v1------v0|
// | | | |
// | |v7---|-|v4
// |/ |/
// v2------v3
var vertices = new Float32Array([ // Vertex coordinates
2.0, 2.0, 2.0, -2.0, 2.0, 2.0, -2.0,-2.0, 2.0, 2.0,-2.0, 2.0, // v0-v1-v2-v3 front
2.0, 2.0, 2.0, 2.0,-2.0, 2.0, 2.0,-2.0,-2.0, 2.0, 2.0,-2.0, // v0-v3-v4-v5 right
2.0, 2.0, 2.0, 2.0, 2.0,-2.0, -2.0, 2.0,-2.0, -2.0, 2.0, 2.0, // v0-v5-v6-v1 up
-2.0, 2.0, 2.0, -2.0, 2.0,-2.0, -2.0,-2.0,-2.0, -2.0,-2.0, 2.0, // v1-v6-v7-v2 left
-2.0,-2.0,-2.0, 2.0,-2.0,-2.0, 2.0,-2.0, 2.0, -2.0,-2.0, 2.0, // v7-v4-v3-v2 down
2.0,-2.0,-2.0, -2.0,-2.0,-2.0, -2.0, 2.0,-2.0, 2.0, 2.0,-2.0 // v4-v7-v6-v5 back
]);
var colors = new Float32Array([ // Colors
1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, // v0-v1-v2-v3 front
1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, // v0-v3-v4-v5 right
1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, // v0-v5-v6-v1 up
1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, // v1-v6-v7-v2 left
1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, // v7-v4-v3-v2 down
1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0 // v4-v7-v6-v5 back
]);
var normals = new Float32Array([ // Normal
0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 0.0, 0.0, 1.0, // v0-v1-v2-v3 front
1.0, 0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 0.0, 0.0, // v0-v3-v4-v5 right
0.0, 1.0, 0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 0.0, // v0-v5-v6-v1 up
-1.0, 0.0, 0.0, -1.0, 0.0, 0.0, -1.0, 0.0, 0.0, -1.0, 0.0, 0.0, // v1-v6-v7-v2 left
0.0,-1.0, 0.0, 0.0,-1.0, 0.0, 0.0,-1.0, 0.0, 0.0,-1.0, 0.0, // v7-v4-v3-v2 down
0.0, 0.0,-1.0, 0.0, 0.0,-1.0, 0.0, 0.0,-1.0, 0.0, 0.0,-1.0 // v4-v7-v6-v5 back
]);
var indices = new Uint8Array([ // Indices of the vertices
0, 1, 2, 0, 2, 3, // front
4, 5, 6, 4, 6, 7, // right
8, 9,10, 8,10,11, // up
12,13,14, 12,14,15, // left
16,17,18, 16,18,19, // down
20,21,22, 20,22,23 // back
]);
// Write the vertex coordinates and color to the buffer object
if (!initArrayBuffer(gl, vertices, 3, gl.FLOAT, 'a_Position'))
return -1;
if (!initArrayBuffer(gl, colors, 3, gl.FLOAT, 'a_Color'))
return -1;
if (!initArrayBuffer(gl, normals, 3, gl.FLOAT, 'a_Normal'))
return -1;
// Create a buffer object
var indexBuffer = gl.createBuffer();
if (!indexBuffer) {
console.log('Failed to create the buffer object');
return false;
}
// Write the indices to the buffer object
gl.bindBuffer(gl.ELEMENT_ARRAY_BUFFER, indexBuffer);
gl.bufferData(gl.ELEMENT_ARRAY_BUFFER, indices, gl.STATIC_DRAW);
return indices.length;
}
function initArrayBuffer(gl, data, num, type, attribute) {
var buffer = gl.createBuffer(); // Create a buffer object
if (!buffer) {
console.log('Failed to create the buffer object');
return false;
}
// Write date into the buffer object
gl.bindBuffer(gl.ARRAY_BUFFER, buffer);
gl.bufferData(gl.ARRAY_BUFFER, data, gl.STATIC_DRAW);
// Assign the buffer object to the attribute variable
var a_attribute = gl.getAttribLocation(gl.program, attribute);
if (a_attribute < 0) {
console.log('Failed to get the storage location of ' + attribute);
return false;
}
gl.vertexAttribPointer(a_attribute, num, type, false, 0, 0);
// Enable the assignment of the buffer object to the attribute variable
gl.enableVertexAttribArray(a_attribute);
gl.bindBuffer(gl.ARRAY_BUFFER, null);
return true;
}