102.二叉树的层序遍历.md

102.二叉树的层序遍历

url

题目

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

• 节点的左子树只包含小于当前节点的数。
• 节点的右子树只包含大于当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

输入:
    2
   / \
  1   3
输出: true
输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

方法

code

js

let levelOrder = root => {
    let ret = [];
    let queue = [root];
    while (queue.length !== 0) {
        let list = [];
        let cnt = queue.length;
        while (cnt-- > 0) {
            let node = queue[0]
            queue = queue.slice(1)
            if (node === null)
                continue;
            list.push(node.val);
            queue.push(node.left);
            queue.push(node.right);
        }
        if (list.length !== 0)
            ret.push(list.slice());
    }
    return ret;
}

go

func levelOrder(root *TreeNode) [][]int {
	var ret [][]int
	q := []*TreeNode{root}
	for len(q) != 0{
		var list []int
		cnt := len(q)
		for cnt > 0 {
			cnt--
			node := q[0]
			q = q[1:]
			if node == nil {
				continue
			}
			list = append(list, node.Val)
			q = append(q, node.Left)
			q = append(q, node.Right)
		}
		if len(list) != 0 {
			ret = append(ret, append([]int{}, list...))
		}
	}
	return ret
}

java

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            ArrayList<Integer> list = new ArrayList<>();
            int cnt = queue.size();
            while (cnt-- > 0) {
                TreeNode node = queue.poll();
                if (node == null)
                    continue;
                list.add(node.val);
                queue.add(node.left);
                queue.add(node.right);
            }
            if (list.size() != 0)
                ret.add(list);
        }
        return ret;
    }
}