java는 두 갈래 나무에 대한 각종 조작을 실현한다

최근에 두 갈래 나무에 대한 조작에 관한 문제를 많이 냈는데 처음에는 어려웠는데 나중에 몇 번 해보니 규칙이 있더라고요.방법은 유일하지 않지만 때로는 생각하기 어려울 때가 있다. 특히 귀속 호출은 다른 사람의 코드를 보는 것이 매우 간단하지만 자신은 모퉁이를 돌지 못할 것이라고 생각하지 못하고 자신이 잊지 않도록 필기를 한다. -_-(제목은 대부분 우객망이나 단추에서 나온 것으로 잘못된 환영 지적이 있을 수 있음) 먼저 두 갈래 나무의 기본 구조는 다음과 같다.

public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }

같은 나무

만약 두 나무가 구조적으로 같고 노드가 같은 값을 가지고 있다면, 두 갈래 나무가 같은 것으로 생각하고 함수를 작성하여 그것이 같은지 확인합니다. 귀속 호출:

public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null && q==null) return true;
        if(p==null || q==null) return false;
        if(p.val !=q.val) return false;
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }

2. 대칭 두 갈래 나무

만약 나무의 왼쪽 나무와 오른쪽 나무의 거울이 대칭적이라면, 이 나무는 대칭적이다.두 갈래 나무를 정해서 거울이 대칭적인지 확인하세요.이것은 두 나무가 대칭을 이루는지 검사하는 것과 같다. 즉, 뿌리 결점이 같고, 왼쪽 나무와 다른 나무의 오른쪽 나무가 같다는 것이다.

    public boolean isSymmetric(TreeNode root) {
        return isMirror(root,root);
    }
    public boolean isMirror(TreeNode p,TreeNode q){
        if(p==null && q==null) return true;
        if(p==null || q==null) return false;
        return (p.val==q.val)&&(isMirror(p.left,q.right)&&isMirror(p.right,q.left));
    }

3. 두 갈래 나무의 최대 깊이를 구한다

두 갈래 나무의 깊이는 뿌리 노드에서 가장 먼 잎 노드까지의 가장 긴 경로의 노드 수이다.두 갈래 나무를 정해 최대 깊이를 찾아라.(1) 반복 호출:

 public int maxDepth(TreeNode root) {
        if(root==null) return 0;
        int leftdepth=maxDepth(root.left);
        int rightdepth=maxDepth(root.right);
        return (leftdepth>=rightdepth? leftdepth :rightdepth)+1;
    }

(2) BFS 폭 우선 검색 트리 너비를 따라 각 레이어에 순차적으로 액세스

public int maxDepth(TreeNode root) {
        if(root==null) return 0;
        Queue<TreeNode> queue=new LinkedList<>();// 
        int depth=0;
        queue.add(root);
        while(!queue.isEmpty()){
            depth++;
            int size=queue.size();
            for(int i=0;i<size;i++){// 
                TreeNode temp=queue.poll();
                if(temp.left!=null) queue.add(temp.left);
                if(temp.right!=null) queue.add(temp.right);
            }
        }
        return depth;
    }

넷째, 두 갈래 나무의 층이 두루 다니다

두 갈래 나무를 정해서 노드 값이 밑에서 위로 올라가는 차원을 되돌려줍니다.(즉 잎 노드가 있는 층에서 뿌리 노드가 있는 층까지 한 층씩 왼쪽에서 오른쪽으로 훑어보기) 예를 들어 두 갈래 나무[3,9,20,null,null,15,7],

   3
  / \
 9  20
   /  \
  15   7

아래에서 위로 올라가는 단계를 되돌려줍니다. [[15,7],[9,20,[3]]

public List<List<Integer>> levelOrderBottom(TreeNode root) {
        Queue<TreeNode> queue =new LinkedList<>();// 
        queue.add(root);
        List<List<Integer>> list=new LinkedList<>();
        if(root==null) return list;
        while(!queue.isEmpty()){
            list.add(0,new ArrayList<>());// 
            int size=queue.size();
            for(int i=0;i<size;i++){
                TreeNode tempNode=queue.poll();
                list.get(0).add(tempNode.val);// val ArrayList
                if(tempNode.left!=null) queue.add(tempNode.left);
                if(tempNode.right!=null) queue.add(tempNode.right);
            }
        }
        return list;
    }

5. 균형 두 갈래 나무

한 그루의 고도 균형 두 갈래 나무는 두 갈래 나무의 각 노드의 좌우 두 개의 하위 나무의 높이 차이의 절대치가 1을 초과하지 않는다고 정의한다.두 갈래 나무를 정해 고도의 균형을 이루는 두 갈래 나무인지 아닌지를 판단한다.하향식 반복:

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null) return true;
        return Math.abs(height(root.left)-height(root.right))<=1 && isBalanced(root.left) && isBalanced(root.right);
    }
    public int height(TreeNode root){// 
        if(root==null)return -1;
        return 1+Math.max(height(root.left),height(root.right));
    }
}

6. 질서수 그룹을 두 갈래 검색 트리로 변환

오름차순으로 배열된 질서수 그룹을 고도 균형 두 갈래 검색 트리로 변환합니다.본고에서 하나의 고도 균형 두 갈래 나무는 한 갈래 나무의 각 노드의 좌우 두 개의 하위 나무의 높이 차이의 절대치가 1을 초과하지 않는 것을 가리킨다.중차순 반복: 항상 중간 위치의 왼쪽 요소를 루트 결점으로 선택

class Solution {
    int [] nums;
    public TreeNode helper(int left,int right){
        if(left>right) return null;
        int p=(left+right)/2;
        /* 
        int p=(left+right)/2;
        if((left+right)%2==1) ++p;*/
        TreeNode root=new TreeNode(nums[p]);
        root.left=helper(left,p-1);
        root.right=helper(p+1,right);
        return root;
    }
    public TreeNode sortedArrayToBST(int[] nums) {
        this.nums=nums;
        return helper(0,nums.length-1);
    }
}

7. 경로 총계

두 갈래 나무와 목표를 정하고 이 나무에 뿌리 노드가 잎 노드까지의 경로가 있는지 판단한다. 이 경로에 있는 모든 노드 값은 목표와 같다.귀속:

public boolean hasPathSum(TreeNode root, int sum) {
    if (root == null)
      return false;

    sum -= root.val;
    if ((root.left == null) && (root.right == null))
      return (sum == 0);
    return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
  }

 ：LeetCode
 ：https://leetcode-cn.com/problems/path-sum/solution/lu-jing-zong-he-by-leetcode/
 ： （LeetCode）
 。 ， 。

교체:

public boolean hasPathSum(TreeNode root, int sum) {
        if(root==null)    return false;
        Queue<TreeNode> nodeQueue=new LinkedList<>();
        Queue<Integer> sumQueue=new LinkedList<>();
        nodeQueue.add(root);
        sumQueue.add(root.val);
        while(!nodeQueue.isEmpty()){
            TreeNode tempNode=nodeQueue.poll();
            int tempSum=sumQueue.poll();
            if((tempNode.left==null)&&(tempNode.right==null)&&(tempSum==sum)) return true;
            if(tempNode.left!=null){
                nodeQueue.add(tempNode.left);
                sumQueue.add(tempSum+tempNode.left.val);
            }
             if(tempNode.right!=null){
                nodeQueue.add(tempNode.right);
                sumQueue.add(tempSum+tempNode.right.val);
            }
        }
        return false;
    }

8. 전차와 중차 재건 두 갈래 나무

두 갈래 나무의 앞 순서와 중간 순서의 결과를 입력하십시오. 이 두 갈래 나무를 다시 만드십시오.입력한 앞 순서와 중간 순서의 결과에 중복된 숫자가 없다고 가정하십시오.예를 들어 앞 순서 반복 시퀀스 {1,2,4,7,3,5,6,8}와 중간 순서 반복 시퀀스 {4,7,2,1,5,3,8,6}를 입력하면 두 갈래 트리를 재건하고 되돌려줍니다.
앞의 순서에 따라 흐르는 성질에 따라 첫 번째 원소는 반드시 루트이다. 중간의 순서에 따라 흐르는 성질에 따라 루트 원소의 앞쪽은 루트의 왼쪽 나무이고 뒤쪽은 루트의 오른쪽 나무이다.

import java.util.Arrays;
public class Solution {
     public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
         if(pre.length == 0) return null;
         TreeNode root = new TreeNode(pre[0]);
         if(pre.length == 1) return root;
         int index = 0;
         for(int i=0;i<in.length;i++){
             if(pre[0] == in[i]){
                 index = i;
                 break;
             }
         }
         root.left=reConstructBinaryTree(Arrays.copyOfRange(pre,1,index+1),Arrays.copyOfRange(in,0,index));
         root.right=reConstructBinaryTree(Arrays.copyOfRange(pre,index+1,pre.length),Arrays.copyOfRange(in,index+1,in.length));
         return root;
    }
}

환영