二叉树的一些操作

反转二叉树

前一段时间国外某大牛面试Google被刷掉，原因是没有能够徒手写出来反转二叉树的代码，在网上看到了一个人的分析代码，特此记下来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        root.left = invertTree(root.left);
        root.right = invertTree(root.right);

        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        return root;
    }
}

遍历二叉树

二叉树的遍历有三种，分别是前序遍历、中序遍历和后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
/**
 * Definition for a binary tree node.
 * public class BinaryTree {
 *     Object element;
 *     TreeNode left;
 *     TreeNode right;
 *     
 * }
 */
public class Solution {
    /** 访问节点 */
　　public static void visit(BinaryTree p) {
　　　　System.out.print(p.getKey() + " ");
　　}
　　/** 递归实现前序遍历 */
　　protected static void preorder(BinaryTree p) {
　　　　if (p != null) {
　　　　　　visit(p);
　　　　　　preorder(p.getLeft());
　　　　　　preorder(p.getRight());
　　　　}
　　}
　　/** 递归实现中序遍历 */
　　protected static void inorder(BinaryTree p) {
　　　　if (p != null) {
　　　　　　inorder(p.getLeft());
　　　　　　visit(p);
　　　　　　inorder(p.getRight());
　　　　}
　　}
　　/** 递归实现后序遍历 */
　　protected static void postorder(BinaryTree p) {
　　　　if (p != null) {
　　　　　　postorder(p.getLeft());
　　　　　　postorder(p.getRight());
　　　　　　visit(p);
　　　　}
　　}
/** 非递归实现前序遍历 */
　　protected static void iterativePreorder(BinaryTree p) {
　　　　Stack<BinaryTree> stack = new Stack<BinaryTree>();
　　　　if (p != null) {
　　　　　　stack.push(p);
　　　　　　while (!stack.empty()) {
　　　　　　　　p = stack.pop();
　　　　　　　　visit(p);
　　　　　　　　if (p.getRight() != null)
　　　　　　　　　　stack.push(p.getRight());
　　　　　　　　if (p.getLeft() != null)
　　　　　　　　　　stack.push(p.getLeft());
　　　　　　}
　　　　}
　　}
　　/** 非递归实现后序遍历 */
　　protected static void iterativePostorder(BinaryTree p) {
        BinaryTree q = p;
　　　　Stack<BinaryTree> stack = new Stack<BinaryTree>();
　　　　while (p != null) {
　　　　　　// 左子树入栈
　　　　　　for (; p.getLeft() != null; p = p.getLeft())
　　　　　　　　stack.push(p);
　　　　　　// 当前节点无右子或右子已经输出
　　　　　　while (p != null && (p.getRight() == null || p.getRight() == q)) {
　　　　　　　　visit(p);
　　　　　　　　q = p;// 记录上一个已输出节点
　　　　　　　　if (stack.empty())
　　　　　　　　　　return;
　　　　　　　　p = stack.pop();
　　　　　　}
　　　　　　// 处理右子
　　　　　　stack.push(p);
　　　　　　p = p.getRight();
　　　　}
　　}
　　/** 非递归实现中序遍历 */
　　protected static void iterativeInorder(BinaryTree p) {
　　　　Stack<BinaryTree> stack = new Stack<BinaryTree>();
　　　　while (p != null) {
　　　　　　while (p != null) {
　　　　　　　　if (p.getRight() != null)
　　　　　　　　　　stack.push(p.getRight());// 当前节点右子入栈
　　　　　　　　stack.push(p);// 当前节点入栈
　　　　　　　　p = p.getLeft();
　　　　　　}
　　　　　　p = stack.pop();
　　　　　　while (!stack.empty() && p.getRight() == null) {
　　　　　　　　visit(p);
　　　　　　　　p = stack.pop();
　　　　　　}
　　　　　　visit(p);
　　　　　　if (!stack.empty())
　　　　　　　　p = stack.pop();
　　　　　　else
　　　　　　　　p = null;
　　　　}
　　}
}

求二叉树的深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * public class BinaryTree {
 *     Object element;
 *     TreeNode left;
 *     TreeNode right;
 *     
 * }
 */
public class Solution {
    public int length(BinaryTree root){
        if(root == null)
            return 0;
        int leftLength = length(root.left);
        int rightLength = length(root.right);
        if(leftLength > rightLength){
            return leftLength + 1;
        }else{
            return rightLength + 1;
        }
    }
}