树

树_05

关于二叉树的定义

    class TreeNode {
            int val;
            TreeNode left, right, next;
        }

计算一颗二叉树有多少节点

    /**
         * 计算一颗二叉树有多少节点
         */
        int count(TreeNode root) {
            if(root == null) {
                return 0;
            }
            return 1 + count(root.left) + count(root.right);
        }

实现一颗二叉树的反转

        /**
         * 实现一颗二叉树的反转
         */
        TreeNode invertTree(TreeNode root) {
            if(root == null) {
                return null;
            }
            //先把 root 两边的子节点反转
            TreeNode tmp = root.left;
            root.left = root.right;
            root.left = tmp;

            //让左右子节点的子节点继续反转
            //此时可以把子节点看成 (root) 节点去理解
            invertTree(root.left);
            invertTree(root.right);

            return root;
        }

连接同一层二叉树相邻的两个节点

       /**
         * 把二叉树的每层节点都用 next 指针连接起来
         * (ERROR) 这个方法有个问题，那就是不属于同一个父节点的两个子节点无法相连
         */
        TreeNode connect(TreeNode root) {
            if(root == null || root.left == null) {
                return root;
            }
            //连接左右两个节点
            root.left.next = root.right;
            //递归遍历左子节点
            connect(root.left);
            //递归遍历右子节点
            connect(root.right);
            return root;
        }

        /**
         * 把二叉树的每层节点都用 next 指针连接起来
         * 是不是可以转化成把相邻的两个节点连接起来，然后借用辅助函数去实现
         */
        TreeNode connects(TreeNode root) {
            if(root == null) {
                return root;
            }
            connectTwoNode(root.left, root.right);
            return root;
        }

        void connectTwoNode(TreeNode n1, TreeNode n2) {
            if(n1 == null || n2 == null) {
                return;
            }
            //连接左右两个节点，这个是关键，这就使得两个节点建立了关系
            n1.next = n2;
            //递归遍历相同父节点的两个子节点
            connectTwoNode(n1.left, n1.right);
            connectTwoNode(n2.left, n2.right);
            //递归遍历跨父节点的两个子节点
            connectTwoNode(n1.right, n2.left);
        }

构建最大二叉树

    public class TreeNode {
            int val;
            TreeNode left, right;

            public TreeNode(int maxVal) {}
        }

        /**
         * 题目的意思是：给定一个不含重复元素的整数数组，构造一颗最大二叉树。
         * 要求是：
         * 1：二叉树的根是数组的最大元素。
         * 2：左子树是数组最大元素左边部分构造出来的最大二叉树。
         * 3：右子树是数组最大元素右边部分构造出来的最大二叉树。
         *
         * 对于构造二叉树，根节点要做的就是想办法把自己构建出来。
         * 其实对于整个数组来说，找到最大值后，余下的部分，又可以看作新的数组，然后在新的数组里在找到最大值，以此循环
         * 根据以上的思路分析，很明显递归方法比较适合
         */

        //伪代码
        TreeNode constructMaxTree01([3,2,1,6,0,5]) {
            TreeNode root = new TreeNode(6);
            //根据题目的意思，很明显 6 已经是树的根了，那么数字 6 左边的就只有是左子树，在 6 的左子树中在继续构造同样的继续递归
            root.left = constructMaxTree01([3,2,1]);
            //6 右边的就只有是右子树，在 6 的右子树中在继续构造同样的继续递归
            root.right = constructMaxTree01([0,5]);
            return root;
        }

        //伪代码在详细一点
        TreeNode constructMaxTree02(int[] nums) {
            if(nums == null) {
                return null;
            }
            //不断寻找最大值的过程
            int maxVal = Integer.MAX_VALUE;
            int index = 0;
            for (int i = 0; i < maxVal; i++) {
                if (nums[i] > maxVal) {
                    maxVal = nums[i];
                    index = i;
                }
            }
            //找到最大值构造树的根，然后递归左，右子树
            TreeNode root = new TreeNode(maxVal);
            //但这这里能明显发觉，在同一个方法中是无法实现的，需要构建一个辅助函数来操作
            //递归左子树
            root.left = constructMaxTree02(nums[0...index-1]);
            //递归右子树
            root.right = constructMaxTree02([index+1...nums.length-1]);
            return root;
        }

        //完整代码
        TreeNode constructMaxTree(int[] nums) {
            return bulid(nums, 0, nums.length - 1);
        }

        TreeNode bulid(int[] nums, int lo, int hi) {
            if(lo > hi) {
                return null;
            }
            int index = -1;
            int maxVal = Integer.MAX_VALUE;
            for (int i = lo; i <= hi; i++) {
                if(nums[i] > maxVal) {
                    maxVal = nums[i];
                    index = i;
                }
            }
            TreeNode root = new TreeNode(maxVal);
            root.left = bulid(nums, lo, index - 1);
            root.right = bulid(nums, index + 1, hi);
            return root;
        }