層序遍歷

非遞歸

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

遞歸

  List<List<Integer>> res = new ArrayList();

public List<List<Integer>> levelOrder(TreeNode root) {
    visit(root, 0);
    return res;
}

public void visit(TreeNode treeNode, int depth) {
    if(treeNode == null) {
        return;
    }
    depth++;
    if(res.size() < depth) {
        List<Integer> list = new ArrayList();
        res.add(list);
    }
    res.get(depth - 1).add(treeNode.val);
    visit(treeNode.left, depth);
    visit(treeNode.right, depth);
}

翻轉(zhuǎn)二叉樹(shù)

遞歸

    public TreeNode invertTree(TreeNode root) {
    if(root == null) {
        return null;
    }
    TreeNode tmp = root.right;
    root.right = root.left;
    root.left = tmp;
    invertTree(root.left);
    invertTree(root.right);
    return root;
}

非遞歸

    public TreeNode invertTree(TreeNode root) {
    Stack<TreeNode> stack = new Stack();
    if(root == null) {
        return null;
    }
    stack.push(root);
    while(!stack.isEmpty()) {
        TreeNode node = stack.pop();
        TreeNode tmp = node.right;
        node.right = node.left;
        node.left = tmp;
        if(node.right != null) {
            stack.push(node.right);
        }
        if(node.left != null) {
            stack.push(node.left);
        }
    }
    return root;
}

    public TreeNode invertTree(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList();
    if(root == null) {
        return null;
    }
    queue.offer(root);
    while(!queue.isEmpty()) {
        TreeNode node = queue.poll();
        TreeNode tmp = node.right;
        node.right = node.left;
        node.left = tmp;
        if(node.right != null) {
            queue.offer(node.right);
        }
        if(node.left != null) {
            queue.offer(node.left);
        }
    }
    return root;
}

  public TreeNode invertTree(TreeNode root) {
Stack<TreeNode> stack = new Stack();
TreeNode cur = root;
while(!stack.isEmpty() || cur != null) {
    if(cur != null) {
        stack.push(cur);
        cur = cur.left;
    } else {
        TreeNode node = stack.pop();
        TreeNode tmp = node.right;
        node.right = node.left;
        node.left = tmp;
        cur = node.left;
    }
}
return root;
}

對(duì)稱二叉樹(shù)

遞歸

    public boolean isSymmetric(TreeNode root) {
    return dfs(root.left,root.right);
}

public boolean dfs(TreeNode left, TreeNode right) {
    if(left ==null && right != null) return false;
    else if (left != null && right == null) return false;
    else if (right == null && left == null) return true;
    else if (right.val != left.val) return false;
    return dfs(left.left, right.right) && dfs(left.right, right.left);
    
}

層序遍歷

    public boolean isSymmetric(TreeNode root) {
     Queue<TreeNode> queue = new LinkedList();

queue.offer(root.left);
queue.offer(root.right);
while(!queue.isEmpty()) {
    TreeNode left = queue.poll();
    TreeNode right = queue.poll();
    if(left==null && right==null ) {
         continue;
    }
    if(left ==null || right == null || right.val != left.val) {
        return false;
    }
    queue.offer(left.left);
    queue.offer(right.right);
    queue.offer(left.right);
    queue.offer(right.left);
}
return true;

}