当前位置: article > 正文

[Java]将二叉树的左右子树交换非递归实现

作者：寸_铁 | 2024-06-19 21:00:44

踩

[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;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/寸_铁/article/detail/737658

[Java]将二叉树的左右子树交换 非递归实现

[Java]将二叉树的左右子树交换非递归实现