问题一:对称的二叉树
请实现一个函数,用来判断一棵二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。
代码如下:
boolean isSymmetrical(TreeNode pRoot) {
if (pRoot == null)
return true;
return isSymmetrical(pRoot.left, pRoot.right);
}
boolean isSymmetrical(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null)
return true;
if (t1 == null || t2 == null)
return false;
if (t1.val != t2.val)
return false;
return isSymmetrical(t1.left, t2.right) && isSymmetrical(t1.right, t2.left);
}
算法描述:
- 用递归函数,当t1的左子树和t2的右子树一致且t1的右子树和t2的左子树一致,则t1和t2对称。
问题二:从上往下打印二叉树
从上往下打印出二叉树的每个节点,同层节点从左至右打印。
代码如下:
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
ArrayList<Integer> ret = new ArrayList<>();
queue.add(root);
while (!queue.isEmpty()) {
int cnt = queue.size();
while (cnt-- > 0) {
TreeNode t = queue.poll();
if (t == null)
continue;
ret.add(t.val);
queue.add(t.left);
queue.add(t.right);
}
}
return ret;
}
算法描述:
- 定义一个队列queue和链表ret;
- 根结点入队列;
- 如果队列不为空,迭代,出队列至t;
- 将t的值压入链表ret,t的左子结点入队列,t的右子结点再入队列;
- 迭代,左子结点出队列,将其值压入ret,右子结点再出队列,再将值压入ret;
- 当队列为空,迭代结束,返回ret,程序结束。
问题三:把二叉树打印成多行
从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。
代码如下:
ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(pRoot);
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;
}
算法描述:
和上题几乎一样。每迭代一次队列,打印出链表中元素,再清空链表。
问题四:按之字形顺序打印二叉树
请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。
代码如下:
public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(pRoot);
boolean reverse = false;
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 (reverse)
Collections.reverse(list);
reverse = !reverse;
if (list.size() != 0)
ret.add(list);
}
return ret;
}
算法描述:
- 和上题类似。每迭代一次队列,如果是奇数次迭代,反转链表,偶数次迭代链表不反转。打印出链表中元素,再清空链表,继续下次迭代。
注:凡属于本公众号内容,未经允许不得私自转载,否则将依法追究侵权责任。