四川网站建设设计,科技类网站,wordpress菜单左对齐,韶关市开发区建设局网站题目链接 : https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/题目描述:给定一个二叉树#xff0c;返回其节点值自底向上的层次遍历。 #xff08;即按从叶子节点所在层到根节点所在的层#xff0c;逐层从左向右遍历#xff09;例如#xff1a; 给…题目链接 : https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/题目描述:给定一个二叉树返回其节点值自底向上的层次遍历。 即按从叶子节点所在层到根节点所在的层逐层从左向右遍历例如 给定二叉树 [3,9,20,null,null,15,7],3/ 9 20/ 15 7返回其自底向上的层次遍历为[[15,7],[9,20],[3]
]思路:与上一题层次遍历一样,只不过输出的顺序取反了!所以只需要从头添加数组就可以了!思路一: 迭代思路二: 递归代码:思路一:# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val x
# self.left None
# self.right Noneclass Solution:def levelOrderBottom(self, root: TreeNode) - List[List[int]]:from collections import dequeif not root: return []queue deque()queue.appendleft(root)res []while queue:tmp []n len(queue)for _ in range(n):node queue.pop()tmp.append(node.val)if node.left:queue.appendleft(node.left)if node.right:queue.appendleft(node.right)res.insert(0, tmp)return resjava/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class Solution {public ListListInteger levelOrderBottom(TreeNode root) {ListListInteger res new LinkedList();if (root null) return res;DequeTreeNode queue new LinkedList();queue.add(root);while (!queue.isEmpty()) {ListInteger tmp new ArrayList();int n queue.size();for (int i 0; i n; i) {TreeNode node queue.poll();tmp.add(node.val);if (node.left ! null) queue.add(node.left);if (node.right ! null) queue.add(node.right);}res.add(0, tmp);}return res; }
}思路二:# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val x
# self.left None
# self.right Noneclass Solution:def levelOrderBottom(self, root: TreeNode) - List[List[int]]:res []def helper(root, depth):if not root: return if depth len(res):res.insert(0, [])res[-(depth1)].append(root.val)helper(root.left, depth1)helper(root.right, depth1)helper(root, 0)return resjava/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class Solution {public ListListInteger levelOrderBottom(TreeNode root){ListListInteger res new LinkedList();helper(res, root, 0);return res;}private void helper(ListListInteger res, TreeNode root, int depth) {if (root null) return;if (res.size() depth) res.add(0, new ArrayList());res.get(res.size() - depth - 1).add(root.val);helper(res, root.left, depth 1);helper(res, root.right, depth 1);}
}一起刷LeetCode - 威行天下 - 博客园www.cnblogs.com
