[GeeksForGeeks] Print all nodes that don't have sibling in a binary tree.

Given a binary tree,  get all nodes that don‘t have sibling node, excluding the root node.

Level order and pre order solutions.

 1 import java.util.ArrayList;
 2 import java.util.LinkedList;
 3 import java.util.Queue;
 4
 5 public class NodeWithoutSibling {
 6     public ArrayList<Integer> getNodesWithoutSiblingLevelOrder (TreeNode root){
 7         if(root == null) {
 8             return null;
 9         }
10         ArrayList<Integer> list = new ArrayList<Integer>();
11         Queue<TreeNode> queue = new LinkedList<TreeNode>();
12         queue.add(root);
13         while(!queue.isEmpty()) {
14             TreeNode curr = queue.poll();
15             if(curr.left != null) {
16                 queue.add(curr.left);
17             }
18             if(curr.right != null) {
19                 queue.add(curr.right);
20             }
21             if(curr.left != null && curr.right == null) {
22                 list.add(curr.left.val);
23             }
24             if(curr.left == null && curr.right != null) {
25                 list.add(curr.right.val);
26             }
27         }
28         return list;
29     }
30
31     public ArrayList<Integer> getNodesWithoutSiblingPreOrder1 (TreeNode root){
32         ArrayList<Integer> list = new ArrayList<Integer>();
33         preOrderHelper1(root, list);
34         return list;
35     }
36     private void preOrderHelper1(TreeNode node, ArrayList<Integer> list) {
37         if(node == null) {
38             return;
39         }
40         if(node.left != null && node.right == null) {
41             list.add(node.left.val);
42         }
43         if(node.left == null && node.right != null) {
44             list.add(node.right.val);
45         }
46         preOrderHelper1(node.left, list);
47         preOrderHelper1(node.right, list);
48     }
49
50     public ArrayList<Integer> getNodesWithoutSiblingPreOrder2 (TreeNode root) {
51         ArrayList<Integer> list = new ArrayList<Integer>();
52         preOrderHelper2(root, list);
53         return list;
54     }
55     private void preOrderHelper2(TreeNode node, ArrayList<Integer> list) {
56         if(node == null) {
57             return;
58         }
59         if(node.left != null && node.right != null) {
60             preOrderHelper2(node.left, list);
61             preOrderHelper2(node.right, list);
62         }
63         else if(node.left != null) {
64             list.add(node.left.val);
65             preOrderHelper2(node.left, list);
66         }
67         else if(node.right != null) {
68             list.add(node.right.val);
69             preOrderHelper2(node.right, list);
70         }
71     }
72
73     public static void main(String[] args) {
74         TreeNode n1 = new TreeNode(1);
75         TreeNode n2 = new TreeNode(2);
76         TreeNode n3 = new TreeNode(3);
77         TreeNode n4 = new TreeNode(4);
78         TreeNode n5 = new TreeNode(5);
79         TreeNode n6 = new TreeNode(6);
80         n1.left = n2; n1.right = n3;
81         n2.right = n4; n3.left = n5; n5.left = n6;
82         NodeWithoutSibling test = new NodeWithoutSibling();
83         ArrayList<Integer> list = test.getNodesWithoutSiblingPreOrder2(n1);
84         for(int i = 0; i < list.size(); i++) {
85             System.out.println(list.get(i));
86         }
87     }
88 }

[GeeksForGeeks] Print all nodes that don't have sibling in a binary tree.

时间: 08-22

[GeeksForGeeks] Print all nodes that don't have sibling in a binary tree.的相关文章

[GeeksForGeeks] Connect binary tree nodes of same level

Given a binary tree with each node having one extra field of nextRight. nextRight points to the next right node of the same level. Initially all nodes' nextRight field are set to null. Connect all nodes at the same level by setting each node's nextRi

[GeeksForGeeks] Print leftmost and rightmost nodes at each level of a binary tree.

Given a Binary Tree, Print the corner nodes at each level. The node at the leftmost and the node at the rightmost. For example, output for following is 15, 10, 20, 8, 25. Solution. Level Order Traversal using queue. Core idea:  Level order traversal

Print all nodes at distance k from a given node

Given a binary tree, a target node in the binary tree, and an integer value k, print all the nodes that are at distance k from the given target node. No parent pointers are available Consider the tree shown in diagram Input: target = pointer to node

Print Nodes in Top View of Binary Tree

Top view of a binary tree is the set of nodes visible when the tree is viewed from the top. Given a binary tree, print the top view of it. The output nodes can be printed in any order. Expected time complexity is O(n) A node x is there in output if x

U面经Prepare: Print Binary Tree With No Two Nodes Share The Same Column

Give a binary tree, elegantly print it so that no two tree nodes share the same column. Requirement: left child should appear on the left column of root, and right child should appear on the right of root. Example: a b c d e f z g h i j 这道题若能发现inorde

[GeeksForGeeks] Remove all half nodes of a given binary tree

Given A binary Tree, how do you remove all the half nodes (which has only one child)? Note leaves should not be touched as they have both children as NULL. For example consider the below tree. Nodes 7, 5 and 9 are half nodes as one of their child is

[geeksforgeeks] Convert a given Binary Tree to Doubly Linked List

http://www.geeksforgeeks.org/in-place-convert-a-given-binary-tree-to-doubly-linked-list/ Given a Binary Tree (Bt), convert it to a Doubly Linked List(DLL). The left and right pointers in nodes are to be used as previous and next pointers respectively

[geeksforgeeks] Bottom View of a Binary Tree

http://www.geeksforgeeks.org/bottom-view-binary-tree/ Bottom View of a Binary Tree Given a Binary Tree, we need to print the bottom view from left to right. A node x is there in output if x is the bottommost node at its horizontal distance. Horizonta

[GeeksForGeeks] Level order traversal in spiral form of a binary tree.

Write a function to print spiral order traversal of a binary tree. For below tree, function should print 1, 2, 3, 4, 5, 6, 7.    Solution. For a normal level order traversal of a binary tree, we traverse every level from left to right. To achieve thi