网站二级目录做网站,删除wordpress logo,海南微信网站制作平台,网站收录了但是搜索不到题目
如何在一棵二叉树中找出它最低层最左边节点的值#xff1f;假设二叉树中最少有一个节点。例如#xff0c;在如图7.5所示的二叉树中最低层最左边一个节点的值是5。
分析
可以用一个变量bottomLeft来保存每一层最左边的节点的值。在遍历二叉树时#xff0c;每当遇到新…题目
如何在一棵二叉树中找出它最低层最左边节点的值假设二叉树中最少有一个节点。例如在如图7.5所示的二叉树中最低层最左边一个节点的值是5。
分析
可以用一个变量bottomLeft来保存每一层最左边的节点的值。在遍历二叉树时每当遇到新的一层时就将变量bottomLeft的值更新为该层第1个节点的值。当整棵二叉树都被遍历完之后变量bottomLeft的值就是最后一次更新的值也就是最后一层的第1个节点的值。
由于用广度优先的顺序遍历二叉树时需要区分不同的层因此可以用两个队列分别存放不同层的节点一个队列存放当前遍历层的节点另一个队列存放下一层的节点。
解
public class Test {public static void main(String[] args) {TreeNode node8 new TreeNode(8);TreeNode node6 new TreeNode(6);TreeNode node10 new TreeNode(10);TreeNode node5 new TreeNode(5);TreeNode node7 new TreeNode(7);TreeNode node9 new TreeNode(9);TreeNode node11 new TreeNode(11);node8.left node6;node8.right node10;node6.left node5;node6.right node7;node10.right node9;node10.right node11;int result findBottomLeftValue(node8);System.out.println(result);}public static int findBottomLeftValue(TreeNode root) {QueueTreeNode queue1 new LinkedList();QueueTreeNode queue2 new LinkedList();queue1.offer(root);int bottomLeft root.val;while (!queue1.isEmpty()) {TreeNode node queue1.poll();if (node.left ! null) {queue2.offer(node.left);}if (node.right ! null) {queue2.offer(node.right);}if (queue1.isEmpty()) {queue1 queue2;queue2 new LinkedList();if (!queue1.isEmpty()) {bottomLeft queue1.peek().val;}}}return bottomLeft;}
}
