二叉树框架技巧以及算法实践

• • • 二叉树的解题思路的理解
    • 实践题
    • • 226.翻转二叉树
      • • 思路分析
        • 代码
      • 114. 二叉树展开为链表
      • • 思路分析
        • 代码
      • 654. 最大二叉树
      • • 思路分析
        • 代码

二叉树的相关的算法，首先就是要搞清楚root要做什么，然后选择进行遍历的方法是前序遍历，中序遍历还是后序遍历

我们观察之后可以得到，每个二叉树的左右子节点交换，结果就是翻转二叉树，所以我们需要在root地方做的就是创建一个临时结点，用临时结点做结点替换，这个题还是比较容易的

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null){
            return null;
        }
        //创建临时结点是为了值的替换
          TreeNode temp = root.left;
          root.left = root.right;
          root.right = temp;
      //进行前序遍历  
          invertTree(root.left);
          invertTree(root.right);
          
          return root;
    }
}

如果要转换为只有右子结点的形式，我们需要把root的左子树和柚子树也调整为只有右子结点的形式，然后将左子树拼接到右子树上

class Solution {
    public void flatten(TreeNode root) {
   if (root == null) return;

    flatten(root.left);
    flatten(root.right); 
     
    TreeNode left = root.left;
    TreeNode right = root.right;

    // 2、将左子树作为右子树  这时左子树已经全部转换成右子节点
    root.left = null;
    root.right = left;

    // 3、将原先的右子树接到当前右子树 
    TreeNode p = root;
    while (p.right != null) {
        p = p.right;
    }
    p.right = right;
    }
}

新建一个TreeNode，选一个最大值填到这个TreeNode里面,然后进行前序遍历，对每个TreeNode都挑选一个最大值填进里面

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return  selectMaxValue(nums,0,nums.length-1);
    }

    public TreeNode selectMaxValue(int[] nums,int l,int r){
        if(l>r){
            return null;
        }

        int maxVal = Integer.MIN_VALUE;
        int index = -1;
        //需要先找到最小值和最小下标
        //这个起始位置是从左侧目标开始的
        for(int i =l;i<=r;i++){
            if(nums[i]>maxVal){
                maxVal = nums[i];
                index = i;  //这里保存下标方便之后使用
            }
        }
        //然后赋值
       TreeNode root = new TreeNode(maxVal);

       root.left = selectMaxValue(nums,l,index-1);
       root.right = selectMaxValue(nums,index+1,r);

       return root;

    } 
}