Java代码实现在一棵二叉链表表示的二叉树中，实现以下操作，并分别采用先根、中根、后根遍历算法。 ① 输入叶子结点。 ② 求二叉树中叶子结点个数。 ③ 将每个结点的左子树与右子树交换。 ④ 验证二叉树的性质3：n0=n2+1。 ⑤ 输出值大于k的结点。 ⑥ 已知先根和中根次序遍历序列构造二叉树。 ⑦ 以广义表表示构造二叉树。 ⑧ 判断两颗二叉树是否相等。 ⑨ 求结点所在的层次。 ⑩ 求一颗二叉树在后根次序遍历下第一个访问的结点。 ⑪ 复制一颗二叉树。 ⑫ 判断一颗二叉树是否为完全二叉树。 ⑬ 实现二叉树后根次序遍历的非递归算法。

1. 输入叶子结点

先根遍历：

void addLeaf(TreeNode root, TreeNode leaf) {
    if (root == null) {
        return;
    }
    if (root.left == null && root.right == null) {
        root.left = leaf;
    } else {
        addLeaf(root.left, leaf);
        addLeaf(root.right, leaf);
    }
}

2. 求二叉树中叶子结点个数

中根遍历：

int countLeaves(TreeNode root) {
    if (root == null) {
        return 0;
    }
    if (root.left == null && root.right == null) {
        return 1;
    }
    return countLeaves(root.left) + countLeaves(root.right);
}

3. 将每个结点的左子树与右子树交换

后根遍历：

void swap(TreeNode root) {
    if (root == null) {
        return;
    }
    swap(root.left);
    swap(root.right);
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
}

4. 验证二叉树的性质3：n0=n2+1

中根遍历：

boolean verifyProperty3(TreeNode root) {
    if (root == null) {
        return true;
    }
    int n0 = 0, n2 = 0;
    Stack<TreeNode> stack = new Stack<>();
    TreeNode node = root;
    while (node != null || !stack.isEmpty()) {
        if (node != null) {
            stack.push(node);
            node = node.left;
        } else {
            node = stack.pop();
            if (node.left == null && node.right == null) {
                n0++;
            } else if (node.left != null && node.right != null) {
                n2++;
            }
            node = node.right;
        }
    }
    return n0 == n2 + 1;
}

5. 输出值大于k的结点

先根遍历：

void printNodes(TreeNode root, int k) {
    if (root == null) {
        return;
    }
    if (root.val > k) {
        System.out.print(root.val + " ");
    }
    printNodes(root.left, k);
    printNodes(root.right, k);
}

6. 已知先根和中根次序遍历序列构造二叉树

TreeNode buildTree(int[] preOrder, int[] inOrder) {
    return buildTreeHelper(preOrder, inOrder, 0, preOrder.length - 1, 0, inOrder.length - 1);
}

TreeNode buildTreeHelper(int[] preOrder, int[] inOrder, int preStart, int preEnd, int inStart, int inEnd) {
    if (preStart > preEnd) {
        return null;
    }
    TreeNode root = new TreeNode(preOrder[preStart]);
    int rootIndex = inStart;
    while (inOrder[rootIndex] != root.val) {
        rootIndex++;
    }
    int leftSize = rootIndex - inStart;
    root.left = buildTreeHelper(preOrder, inOrder, preStart + 1, preStart + leftSize, inStart, rootIndex - 1);
    root.right = buildTreeHelper(preOrder, inOrder, preStart + leftSize + 1, preEnd, rootIndex + 1, inEnd);
    return root;
}

7. 以广义表表示构造二叉树

TreeNode buildTree(String s) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode root = null;
    boolean isLeft = true;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(') {
            isLeft = true;
        } else if (c == ')') {
            stack.pop();
        } else {
            int j = i;
            while (j < s.length() - 1 && Character.isDigit(s.charAt(j + 1))) {
                j++;
            }
            TreeNode node = new TreeNode(Integer.parseInt(s.substring(i, j + 1)));
            if (root == null) {
                root = node;
            } else if (isLeft) {
                stack.peek().left = node;
                isLeft = false;
            } else {
                stack.peek().right = node;
            }
            stack.push(node);
            i = j;
        }
    }
    return root;
}

8. 判断两颗二叉树是否相等

先根遍历：

boolean isEqual(TreeNode root1, TreeNode root2) {
    if (root1 == null && root2 == null) {
        return true;
    }
    if (root1 == null || root2 == null) {
        return false;
    }
    if (root1.val != root2.val) {
        return false;
    }
    return isEqual(root1.left, root2.left) && isEqual(root1.right, root2.right);
}

9. 求结点所在的层次

先根遍历：

int getNodeLevel(TreeNode root, TreeNode node, int level) {
    if (root == null) {
        return 0;
    }
    if (root == node) {
        return level;
    }
    int leftLevel = getNodeLevel(root.left, node, level + 1);
    if (leftLevel != 0) {
        return leftLevel;
    }
    return getNodeLevel(root.right, node, level + 1);
}

10. 求一颗二叉树在后根次序遍历下第一个访问的结点

后根遍历：

TreeNode getFirstVisitNode(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode lastVisit = null;
    TreeNode node = root;
    while (node != null || !stack.isEmpty()) {
        if (node != null) {
            stack.push(node);
            node = node.left;
        } else {
            TreeNode peekNode = stack.peek();
            if (peekNode.right != null && lastVisit != peekNode.right) {
                node = peekNode.right;
            } else {
                lastVisit = stack.pop();
                if (lastVisit.left == null && lastVisit.right == null) {
                    return lastVisit;
                }
            }
        }
    }
    return null;
}

11. 复制一颗二叉树

先根遍历：

TreeNode copyTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    TreeNode newRoot = new TreeNode(root.val);
    newRoot.left = copyTree(root.left);
    newRoot.right = copyTree(root.right);
    return newRoot;
}

12. 判断一颗二叉树是否为完全二叉树

层次遍历：

boolean isCompleteTree(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    boolean hasNull = false;
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        if (node == null) {
            hasNull = true;
        } else {
            if (hasNull) {
                return false;
            }
            queue.offer(node.left);
            queue.offer(node.right);
        }
    }
    return true;
}

13. 实现二叉树后根次序遍历的非递归算法

List<Integer> postOrder(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode lastVisit = null;
    TreeNode node = root;
    while (node != null || !stack.isEmpty()) {
        if (node != null) {
            stack.push(node);
            node = node.left;
        } else {
            TreeNode peekNode = stack.peek();
            if (peekNode.right != null && lastVisit != peekNode.right) {
                node = peekNode.right;
            } else {
                lastVisit = stack.pop();
                result.add(lastVisit.val);
                node = null;
            }
        }
    }
    return result;
}