首页 > 编程语言 >代码随想录算法训练营day18 | leetcode 513.找树左下角的值 ● 112. 路径总和 113.路径总和ii ● 106.从中序与后序遍历序列构造二叉树

代码随想录算法训练营day18 | leetcode 513.找树左下角的值 ● 112. 路径总和 113.路径总和ii ● 106.从中序与后序遍历序列构造二叉树

时间:2023-02-05 15:13:37浏览次数:56  
标签:right return 后序 int 路径 随想录 left 节点 总和

LeetCode 513.找树左下角的值

分析1.0

二叉树的 最底层 最左边 节点的值,层序遍历获取最后一层首个节点值,记录每一层的首个节点,当没有下一层时,返回这个节点

class Solution {
    ArrayDeque<TreeNode> queue = new ArrayDeque();
    int res = 0;
    public int findBottomLeftValue(TreeNode root) {
        queue.offer(root);
        return levelOrder(root);
    }

    public int levelOrder(TreeNode p){
        while(!queue.isEmpty()){
            int size = queue.size();
            int cnt = 0;
            res = queue.peek().val;
            // System.out.println("每层第一个节点"+res);
            while(cnt++ < size){
                p = queue.poll();
                if(p.left != null){
                    queue.offer(p.left);
                }
                if(p.right != null){
                    queue.offer(p.right);
                }
            }
        }
        return res;
    }
}

LeetCode 112. 路径总和

分析1.0

先序遍历递归,记录走过节点和,若==targetSum return; 否则删除节点值

递归

class Solution {
    int sum = 0;
    ArrayList<Integer> list = new ArrayList();
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null){
            return false;
        }
        preOrder(root);
        return list.contains(targetSum);
    }
    public void preOrder(TreeNode p){
        sum += p.val;
        if(p.left == null && p.right == null){
            //System.out.println("sum--------"+sum);
            list.add(sum);
            return;
        }
        if(p.left!=null){
            preOrder(p.left);
            sum -= p.left.val;
        }
        if(p.right!=null){
            preOrder(p.right);
            sum -= p.right.val;
        }
    }
}

论递归有返回值时,某路径和为targetSum时,各级递归该如何返回

if (cur->left) { // 左
    count -= cur->left->val; // 递归,处理节点;
    if (traversal(cur->left, count)) return true;
    count += cur->left->val; // 回溯,撤销处理结果
}
if (cur->right) { // 右
    count -= cur->right->val; // 递归,处理节点;
    if (traversal(cur->right, count)) return true;
    count += cur->right->val; // 回溯,撤销处理结果
}
return false;

LeetCode 106.从中序与后序遍历序列构造二叉树

分析1.0

重要理论知识

切割后的左右子树,在前后序两个数组中元素大小是一致的

重要条件:

  • inorder 和 postorder 都由 不同 的值组成

后序遍历 左右根 所以每棵树的后序数组的最后一个节点为树根

  1. 从后序数组找到这棵树的树根,用其分割中序数组,使原中序数组变为新的两个中序数组-即两棵子树
  2. 子树的大小是一致的,即可利用此特点在后序数组中找到两棵树分别对应的后序遍历序列 第一个是左子树 第二个是右子树 顺序不要弄反
  3. 再从后序序列获取新的根节点...
  4. ......
  5. 直到后序数组只剩一个节点,处理完这个节点就返回

  getInIndex(); return 两棵子树在中序数组中的索引

  getPostIndex(); return 左右子树的新的根节点索引 左边一堆为左子树 右边一堆为右子树

失误

没课树都有post in order,当postOrder只剩一个节点时,意味着这棵树只有一个根节点了,让它做父节点合适的儿子

递归前要进行一次判断,这个节点能否满足递归条件

分析2.0

class Solution {
    //int testCount = 1;
    public TreeNode buildTree(int[] inorder, int[] postorder) {

       return  getRootIndex(inorder, postorder, 0, inorder.length - 1, 0, postorder.length-1);
    }

    public TreeNode getRootIndex(int[] inorder, int[] postorder, int inLeftIndex, int inRightIndex,int postLeftIndex,int postRightIndex){
        //System.out.println(testCount++ +"次访问");
        // 只剩一个后序节点了
        if(postRightIndex==postLeftIndex){
            return new TreeNode(postorder[postRightIndex]);
        }
        // 后序根节点在中序中的索引
        int mid = getIndex(inorder, postorder[postRightIndex]);
        // 左子树中序新索引范围
        int leftTreeLeftIndex = inLeftIndex;
        int leftTreeRightIndex = mid-1;
        // 右子树中序新索引范围
        int rightTreeLeftIndex = mid+1;
        int rightTreeRightIndex = inRightIndex;
        /* 找左右子树的后序索引范围
           左子树-右子树-根节点
           左子树 leftTreeRightIndex - leftTreeLeftIndex + 1
           右子树 rightTReeRightIndex - rightTreeLeftIndex + 1        
        */   
        //int leftTreeSize = leftTreeRightIndex - leftTreeLeftIndex + 1;
        int rightTreeSize = rightTreeRightIndex - rightTreeLeftIndex + 1;
        int leftTreePostOrderLeftIndex = postLeftIndex;
        int leftTreePostOrderRightIndex = postRightIndex - rightTreeSize - 1;
        int rightTreePostOrderLeftIndex = postRightIndex - rightTreeSize;
        int rightTreePostOrderRightIndex = postRightIndex - 1;
        TreeNode root = new TreeNode(postorder[postRightIndex]);
        if(leftTreePostOrderRightIndex>=leftTreePostOrderLeftIndex){
            root.left = getRootIndex(inorder, postorder,leftTreeLeftIndex, leftTreeRightIndex,leftTreePostOrderLeftIndex,leftTreePostOrderRightIndex);
        }
        if(rightTreePostOrderRightIndex>=rightTreePostOrderLeftIndex){
            root.right = getRootIndex(inorder, postorder,rightTreeLeftIndex, rightTreeRightIndex,rightTreePostOrderLeftIndex,rightTreePostOrderRightIndex);   
        }
        return root; 
    }

    // 在指定数组中找指定元素的索引
    public int getIndex(int[] arr, int target){
        for(int i = 0; i < arr.length; i++){
            if(arr[i] == target){
                return i;
            }
        }
        return -1;
    }
}

总结

  1. 递归函数什么时候需要返回值?什么时候不需要返回值?视递归是否需要处理返回值分析

  2. 和单纯的深度遍历不一样,在处理树回溯问题时要先判断当前节点是否为空,非null才能进入递归

  3. 如果知道了目标和,可以目标和-节点值,判断最后结果是否为0 (而不是累加节点值判断和是否为目标和)
  4. 回溯结束就可以处理返回值了!!!
  5. 递归进入条件、递归结束条件
  6. 树的先序后序遍历序列对应的节点数是一致的 非常关键的解题信息

常用变量名增量更新

size、val、ans、cnt、cur、pre、next、left、right、index、gap、tar、res、src、len、start、end、flag、ch、var

 

标签:right,return,后序,int,路径,随想录,left,节点,总和
From: https://www.cnblogs.com/cupxu/p/17092066.html

相关文章