二叉树

发布： 分类： 评论： 阅读：

二叉树结构的定义

1
2
3
4
5
6
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

二叉树的遍历

leetcode 144 . 二叉树的先序遍历

1
2
3
4
5
6
7
8
9
10
11
12
public void preorder(TreeNode node, List<Integer> res) {
   if(node==null)  // 终止条件
       return;     
   res.add(node.val);         // 先序遍历，访问到当前节点，需要执行的操作
   preorder(node.left, res);  // 访问左子节点
   preorder(node.right, res); // 访问右子节点
} 
public List<Integer> preorderTraversal(TreeNode root) {
 List<Integer> res = new ArrayList<>();
 preorder(root, res);
 return res;
}

leetcode 94. 二叉树的中序遍历

1
2
3
4
5
6
7
public void inorder(TreeNode node, List<Integer> res) {
   if(node==null)  // 终止条件
       return;           
   preorder(node.left, res);  // 访问左子节点
   res.add(node.val);         // 中序遍历，访问到当前节点，需要执行的操作
   preorder(node.right, res); // 访问右子节点
}

leetcode 145. 二叉树的后序遍历

1
2
3
4
5
6
7
public void postorder(TreeNode node, List<Integer> res) {
    if(node==null)  // 终止条件
        return;           
    preorder(node.left, res);   // 访问左子节点
    preorder(node.right, res);  // 访问右子节点
    res.add(node.val);          // 后序遍历，访问到当前节点，需要执行的操作
}

leetcode 102. 二叉树的层次遍历

要注意用两个临时变量 node_count 和 next_count 来记录当前层和下一层节点的数量

以前我想的方法是当队列中访问到null节点时表示当前层已经访问完，显然这不是一个好的方法，尤其是到最后一层，下一层都是null了，那么就还要加条件判断当前层节点个数是不是空，就很麻烦。

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
public List<List<Integer>> levelOrder(TreeNode root) {
   List<List<Integer>> result = new ArrayList<>();
   if(root==null) return result;   // 别忘了二叉树为空的特殊情况处理

   List<Integer> tmp_res = new ArrayList<>();
   Queue<TreeNode> que = new LinkedList();   // 用队列来暂存二叉树的节点
   que.add(root);
   int node_count = 1;    // 用来表示当前层节点个数
   int next_count = 0;    // 用来表示下一层节点个数
   while(!que.isEmpty()) {
       TreeNode tmp_node = que.remove();
       tmp_res.add(tmp_node.val);
       node_count -= 1;
       if(tmp_node.left!=null) {   // 左子节点不为空，将左子节点加入队列
         que.add(tmp_node.left);
         next_count += 1;
       }
       if(tmp_node.right!=null) {  // 右子节点不为空，将右子节点加入队列
         que.add(tmp_node.right);
         next_count += 1;
       }
       if(node_count==0) {   //表示当前层已经访问完
         node_count = next_count;
         next_count = 0;
         result.add(tmp_res);
         tmp_res = new ArrayList<>();
       }
   }
   return result;
}

二叉树例题

二叉树给定任意一个节点，找出其中序遍历的下一个节点（剑指 offer）：

题目描述：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

1
2
3
4
5
6
7
8
9
        1
      /   \
     2     3
   /  \   / \
  4    5 6   7
 /    / \    
14   8   9   
   /  \   
  10  11

如上图所示，其中序遍历结果为：[14, 4, 2, 10, 8, 11, 5, 9, 1, 6, 3, 7, 9 ]

  • 因为是中序遍历，所以当前节点的下一个节点必然在其右子树中产生。只需要考虑有没有右子树即可，而不用再去考虑当前节点是不是存在左子树。因为访问到当前节点的时候，其左子树肯定已经都访问完了。
  • 如果它存在右子树，则其中序遍历的下一个节点是右子树的最左子节点 […2, 10…]；[…1, 6…]
  • 节点4无右子树，且它为其父节点2的左子节点，则其中序遍历的下一个节点是其父节点。[…4, 2…]
  • 节点9无右子树，且它为其父节点5的右子节点，则其中序遍历的下一个节点要沿着指向父节点的指针不断向上找，直到找到一个视其父节点为左子节点的节点。[…9, 1…]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public TreeNode getInorderNext(TreeNode node) {
    if(node==null)
         return null;
    if(node.right!=null) {   // 如果右子树不为空，返回右子树的最左子节点
         TreeNode tmp_node = node.right;
         while(tmp_node.left!=null)
            tmp_node = tmp_node.left;
         return tmp_node;
    }
    else if(node.father!=null) {   // 如果右子树为空
        while(node.father!=null && node.father.right==node) {
            node = node.father;
        }
        return node.father;
    }
    else
        return null;
}

leetcode 105. 根据先序遍历和中序遍历确定二叉树的结构：

输入：

1
2
preorder = [3,9,20,15,7]
inorder  = [9,3,15,20,7]

分析：preorder中先访问的是根节点，那么在inorder中找到根节点的位置，然后iorder根节点左侧的即为其左子树，右侧的即为其右子树，然后递归进行该过程即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int pre_index = 0;
public static TreeNode buildTree(int[] preorder, int[] inorder, int left, int right) {
  if(left>=right)
    return null;
  TreeNode node = new TreeNode(preorder[pre_index]);  // 建立当前节点
  int index = -1;
  for(int i=left;i<right;i++) {   // 找到preorder中当前节点在inoder中的位置
    if(inorder[i]==preorder[pre_index])
      index = i;
  }
  pre_index += 1;
  node.left = buildTree(preorder, inorder, left, index);     // 递归inorder中当前节点的左侧节点
  node.right = buildTree(preorder, inorder, index+1, right); // 递归inorder中当前节点的右侧节点
  return node;
}

leetcode 106. 根据后序遍历和中序遍历确定二叉树的结构：

输入：

1
2
inorder   = [9,3,15,20,7]
postorder = [9,15,7,20,3]

分析：因为是后序遍历，所以postorder要从后向前看，最右一个是根节点，然后逐渐向前遍历。postorder中从后向前访问根节点，那么在inorder中找到根节点的位置，然后iorder根节点左侧的即为其左子树，右侧的即为其右子树，然后递归进行该过程即可。

注意：3题和4题最后两个递归循环的顺序是不一样的，后序遍历中，因为是从后向前遍历postorder， 所以它会先访问右子树，所以递归循环时要先建立右子树，再建立左子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int post_index = 0;
public TreeNode buildTree(int[] postorder, int[] inorder, int left, int right) {
    if(left>=right)
    	return null;

    TreeNode node = new TreeNode(postorder[post_index]);
    int index = -1;
    for(int i=left;i<right;i++) {
        if(inorder[i]==postorder[post_index])
            index = i;
    }
    post_index -= 1;
    node.right = buildTree(postorder, inorder, index+1, right);
    node.left = buildTree(postorder, inorder, left, index);
    return node;
}

public TreeNode buildTree(int[] inorder, int[] postorder) {
    post_index = postorder.length-1;
    TreeNode node = buildTree(postorder, inorder, 0, inorder.length);
    return node;
}

leetcode 100. 判断两棵二叉树是否相等：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean judge(TreeNode n1, TreeNode n2) {
    if(n1==null && n2==null)
       return true;
    else if(n1==null || n2==null)
       return false;
    if(n1.val!=n2.val)
       return false;

    return (judge(n1.left, n2.left) && judge(n1.right, n2.right));
}
    
public boolean isSameTree(TreeNode p, TreeNode q) {
    return preorder(p, q);
}

leetcode 101. 判断二叉树是不是对称的：

一种方法，就是判断二叉树镜像之后和自己是不是相等。如果相等就是对称的。但是那样有点太麻烦了。

1
2
3
4
5
      1
    /   \
   2     2
 /  \   /  \
4    3 3    4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean judge(TreeNode left, TreeNode right) {
    if(left==null && right==null)
        return true;
    else if(left==null || right==null)
        return false;
    if(left.val!=right.val)
        return false;

    return (judge(left.left, right.right) && judge(left.right, right.left));
}

public boolean isSymmetric(TreeNode node) {
    if(node==null)
        return true;
    return judge(node.left, node.right);
}

我们可以看到第五题和第六题很相似，只是在递归的时候传的参数不一样。

leetcode 226. 二叉树的镜像：

1
2
3
4
5
      1          |          1
    /   \        |        /   \
   2     3       |       3     2
 /  \   / \      |      / \   /  \
4    5 6   7     |     7   6 5    4
1
2
3
4
5
6
7
8
9
10
11
12
public static TreeNode SymmetricTree(TreeNode node) {
    if(node==null)
       return null;
    if(node.left==null && node.right==null)
       return node;
    TreeNode tmp = node.left;   // 左右节点交换
    node.left = node.right;
    node.right = tmp;
    SymmetricTree(node.left);
    SymmetricTree(node.right);
    return node;
}

完全二叉树

leetcode 222. 完全二叉树的节点个数

  • 完全二叉树和普通二叉树的区别就在于，除了最后一层可能不满以外，其他层全都是满的。
  • 所以想要查完全二叉树的节点个数，除了和普通的方法一样，遍历一遍，只需要知道完全二叉树的层数，和最后一层的节点个数就行了。前面可以用公式 $2^n-1$ 即可。n为前面满二叉树的层数。
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
public int get_num(TreeNode node, int num) {
    if(node==null)
        return 0;
    if(num==1) {
        if(node.left!=null && node.right!=null) return 2;
        else if(node.left!=null) return 1;
        else return 0;
    }
    return get_num(node.left, num-1) + get_num(node.right, num-1);
}

public int countNodes(TreeNode root) {
    TreeNode left = root;
    TreeNode right = root;
    int num_left = 0;
    while(left!=null) {   // 通过左子节点计算二叉树的层数。
        num_left += 1;
        left = left.left;
    }
    int num_right = 0;
    while(right!=null) {  // 从右侧计算二叉树的层数。
        num_right += 1;
        right = right.right;
    }
    // 如果左侧层数和右侧计算的层数相等，那么这是一棵满二叉树。直接用公式计算节点数即可。
    if(num_left==num_right) return (int)Math.pow(2, num_left)-1;
    // 如果不是满二叉树，那么用公式计算前num_right层，然后递归计算最后一层的数目即可。
    else return (int)(Math.pow(2, num_right)-1 + get_num(root, num_right));
}

leetcode 958. 判断一棵二叉树是不是完全二叉树

  • 联想堆，堆就是一棵完全二叉树，堆排序中我们知道，堆可以用一个数组表示，所以完全二叉树也可以由一个数组表示，第 k 个节点的儿子节点是 2k 和 2k+1，那么我们就可以在遍历二叉树的时候给每个节点一个编号，如果最后一层最右侧的节点的编号和二叉树节点个数相等，那么就说明他是一棵完全二叉树。
1
2
3
4
5
      1          |          1
    /   \        |        /   \
   2     3       |       2     3
 /      / \      |      / \  	
4      6   7     |     4   5
  • 如上图所示，按照编号左侧最后一层最右节点编号为7，但二叉树只有6个节点，所以其不是一棵完全二叉树。右面的二叉树，最后一层最右节点编号为5，而二叉树有5个节点，所以是完全二叉树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int num = 0;  // 二叉树节点个数
int final_index = 0;  // 最后一个节点的编号

public void dfs(TreeNode node, int index) {
    if(node==null)
        return;
    num += 1;
    if(node.left==null && node.right==null) 
        final_index = index>final_index?index:final_index;
    dfs(node.left, index*2);
    dfs(node.right, index*2+1);
}

public boolean isCompleteTree(TreeNode root) {
    dfs(root, 1);
    if(final_index==num)  return true;
    else return false;
}

二叉搜索树

leetcode 98. 判断一棵二叉树是不是二叉搜索树

  • 二叉搜索树的中序遍历是有序的，只要判断中序遍历时当前值是不是大于前一个值就行了
  • 下面的代码，本来没设置num来标记是不是第一个节点。直接第一个节点和 Integer.MIN_VALUE 就好了，谁知道测试用例有第一个值是 Integer.MIN_VALUE 的，没办法又多设置了一个变量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
boolean flag = true;
int num = 0;
int tmp_value = Integer.MIN_VALUE;

public void preorder(TreeNode node) {
    if(node==null || flag == false)
        return;
    preorder(node.left);

    if(num!=0 && node.val<=tmp_value) {
        flag = false;
        return;
    }
    else  {
        tmp_value = node.val;
        num += 1;
    }
    preorder(node.right);
}

public boolean isValidBST(TreeNode root) {
    preorder(root);
    return flag;
}

leetcode 108. 将排序数组转为平衡的二叉搜索树

1
2
3
4
5
6
7
8
9
Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5
  • 很简单，每次选取中间节点作为当前节点，然后递归调用就好了。
1
2
3
4
5
6
7
8
9
10
11
12
13
public TreeNode BST(int[] nums, int begin, int end) {
    if(begin>=end)
        return null;
    int mid = (begin + end)/2;
    TreeNode node = new TreeNode(nums[mid]);
    node.left = BST(nums, begin, mid);
    node.right = BST(nums, mid+1, end);
    return node;
}

public TreeNode sortedArrayToBST(int[] nums) {
    return BST(nums, 0, nums.length);
}

leetcode 109. 将排序链表转为平衡的二叉搜索树

  • 跟上道题是一样的，只不过由排序数组改为了排序链表。
  • 方法一：把链表中的内容先存到数组中，再用9.2题的方法。
  • 方法二：直接用链表去找中间节点，其他方法同9.2。找中间节点的方法就是设置快慢指针。一个每次走一步，一个每次走两步。第一个到达尾部时，第二个指向中间节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public TreeNode BST(ListNode begin, ListNode end) {
    if(begin==end)
        return null;

    ListNode slow = begin;
    ListNode fast = begin;
    while(fast!=end && fast.next!=end) {
        slow = slow.next;
        fast = fast.next.next;
    }

    TreeNode node = new TreeNode(slow.val);
    node.left = BST(begin, slow);
    node.right = BST(slow.next, end);
    return node;
}

public TreeNode sortedListToBST(ListNode head) {
    return BST(head, null);
}

Z字形打印二叉树：

二叉搜索树：

给定一个数组，判断该数组是不是二叉搜索树的后序遍历结果：

二叉搜索树转为双向链表：