[Java]将二叉树的左右子树交换 非递归实现
生活随笔
收集整理的这篇文章主要介绍了
[Java]将二叉树的左右子树交换 非递归实现
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
[java] view plaincopy
package dataStruct; import java.util.Stack; /** * 将二叉树的左右子树交换 非递归实现 * @author YangYi */ public class SwapTree { private static Stack<Node> stack = new Stack<Node>(); public static void main(String args[]) { Node root = buildTree(); inOrderVisit(root); swapTree(root); System.out.println(); inOrderVisit(root); } public static void inOrderVisit(Node root) { if (root == null) return; inOrderVisit(root.left); System.out.print(root.data); inOrderVisit(root.right); } public static void swapTree(Node root) { if (root == null) return; Node temp = null; stack.push(root); while (!stack.isEmpty()) { Node node = stack.peek(); if (node.left == null && node.right == null) { node.visited = true; stack.pop(); continue; } if (node.left != null) { if (!node.left.visited) { stack.push(node.left); } } if ((node.left == null || node.left.visited) && node.right != null) { if (!node.right.visited) { stack.push(node.right); } } if ((node.left == null || node.left.visited) && (node.right == null || node.right.visited)) { temp = node.left; node.left = node.right; node.right = temp; node.visited = true; stack.pop(); } } } public static Node buildTree() { Node root = new Node(); root.data = 1; Node temp = new Node(); temp.data = 2; root.left = temp; temp = new Node(); temp.data = 3; root.right = temp; temp = new Node(); temp.data = 4; root.right.right = temp; temp = new Node(); temp.data = 5; root.left.right = temp; temp = new Node(); temp.data = 6; root.left.right.right = temp; return root; } } class Node { boolean visited = false; int data = 0; Node left = null; Node right = null; }
总结
以上是生活随笔为你收集整理的[Java]将二叉树的左右子树交换 非递归实现的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇： SQL经典面试题及答案
- 下一篇： Java 多线程 并发编程------超