二叉树的建立

整数数组转二叉树

下面只是一个简单的示例，没考虑某个子树为空的情况。把{1, 2, 3, 21, 22, 31, 32} 转变为一个二叉树。

import java.util.ArrayList;
import java.util.List;

public class TreeTest {
    //tree struct
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    public static void main(String[] args) {

        int[] a = {1, 2, 3, 21, 22, 31, 32};
        
        //最终循环体执行的是节点，而不是整数值，所以要先把数组转为节点列表，然后遍历
        List<TreeNode> list = new ArrayList<>();
        for (int i = 0; i < a.length; i++) {
            TreeNode t = new TreeNode(a[i]);
            list.add(t);
        }

        for (int i = 0; i < list.size(); i++) {
             //增加判空，因为可能只有左子树，或者只有右子树
            if (2 * i + 1 < list.size() && list.get(2 * i + 1) != null) { 
                list.get(i).left = list.get(2 * i + 1);
            }

            if (2 * i + 2 < list.size() && list.get(2 * i + 2) != null) {
                list.get(i).right = list.get(2 * i + 2);
            }
		}
		
        printNode(list.get(0));
    }

    public static void printNode(TreeNode n) { //先序输出
        if (n != null) {
            System.out.print(" " + n.val);
            printNode(n.left);
            printNode(n.right);
        }
    }
}

输出结果：

 1 2 21 22 3 31 32

Object数组转二叉树

要考虑某个节点为空的情况，如下图，数组表示为[1,null,2,null,null,3,null]，就要使用Object数组。

在leetcode94题中，上图用数组表示为[1,null,2,3]，这种表示是不严谨的。不必要纠结这个点，理解根据数组创建二叉树的原理，能自己创建二叉树就好。后面学到二叉树的序列化，再分析。

import java.util.ArrayList;
import java.util.List;

public class TreeTest2 {
    //tree struct
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    public static void main(String[] args) {

        Object[] a = {1, null, 2, null, null, 3, null};
        List<TreeNode> list = new ArrayList<>();
        for (int i = 0; i < a.length; i++) {
            if (a[i] != null) {
                TreeNode t = new TreeNode((int) a[i]);
                list.add(t);
            } else {
                list.add(null);
            }
        }

        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) == null) {// i=2
                continue;
            }
			 //增加判空，因为可能只有左子树，或者只有右子树
            if ((2 * i + 1) < list.size() && list.get(2 * i + 1) != null) {
                list.get(i).left = list.get(2 * i + 1);
            }

            if ((2 * i + 2) < list.size() && list.get(2 * i + 2) != null) {
                list.get(i).right = list.get(2 * i + 2);
            }

        }

        printNode(list.get(0));

    }

    public static void printNode(TreeNode n) {
        /**
         *        1
         *   null    2
         *         3   null
         */
        if (n != null) {
            System.out.print(" " + n.val);
            printNode(n.left);
            printNode(n.right);
        }
    }
}

输出：

1 2 3

二叉树的遍历

leetcode94.二叉树的中序遍历

题目描述

    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        list = put(root, list);
        return list;
    }

    public static List<Integer> put(TreeNode r, List<Integer> list) {
        if (r != null) {
            list = put(r.left, list);
            list.add(r.val);
            list = put(r.right, list);
        }
        return list;
    }
}

leetcode144.二叉树的前序遍历

题目描述

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        addElement(root,list);
        return list;
    }

    public List<Integer> addElement(TreeNode node, List<Integer> list) {
        if (node != null) {
            list.add(node.val);
            addElement(node.left, list);
            addElement(node.right, list);
        }
        return list;
    }
}