나무의 기초 계산법 문제
69710 단어 데이터 구조 와 알고리즘이 진 트 리데이터 구조
3 부작 으로 귀속:
1. 이 진 트 리 옮 겨 다 니 기
1. 재 귀적 버 전
1. 앞 순 서 를 옮 겨 다 니 기;먼저 뿌리 노드 에 접근 한 다음 에 왼쪽 트 리 에 접근 하고 마지막 으로 오른쪽 트 리 에 접근 합 니 다. 2. 중간 순서 로 옮 겨 다 니 기;먼저 왼쪽 트 리 를 방문 하고 중간 에 뿌리 노드 를 방문 한 다음 에 오른쪽 트 리 를 방문 합 니 다.이 방식 은 결 과 를 옮 겨 다 니 며 결점 을 질서 있 게 한다.먼저 왼쪽 트 리 에 접근 한 다음 오른쪽 트 리 에 접근 하고 마지막 으로 루트 노드 에 접근 합 니 다.
// 3 ，
public void values(TreeNode root) {
preErgodic(root);
midErgodic(root);
afterErgodic(root);
}
/**
* ：
* 1. ;
* 2. ， ，
* 3. ， ，
*/
private void preErgodic(TreeNode node) {
if (node == null) return;// ，
System.out.println(node.val);//
if (node.left != null) preErgodic(node.left);//
if (node.right != null) preErgodic(node.right);//
}
/**
* ：
* 1. ， ，
* 2. ;
* 3. ， ，
*/
private void midErgodic(TreeNode node) {
if(node==null) return;
if(node.left!=null) midErgodic(node.left);
System.out.println(node.val);//
if(node.right!=null) midErgodic(node.right);
}
/**
* ：
* 1. ， ，
* 2. ， ，
* 3. ;
*/
private void afterErgodic(TreeNode node) {
if(node == null) return;
if(node.left!=null) afterErgodic(node.left);
if(node.right!=null) afterErgodic(node.right);
System.out.println(node.val);
}
2. 비 재 귀적 버 전
사상: 스 택 을 사용 합 니 다. 재 귀 버 전 은 시스템 이 스 택 을 눌 러 주 는 것 이기 때문에 우리 가 비 재 귀 버 전 을 사용 하면 스스로 수 동 으로 스 택 을 눌 러 줄 수 있다 고 생각 할 수 있 습 니 다.
앞 순 서 를 옮 겨 다 니 기: 하나의 스 택 을 사용 하여 먼저 뿌리 노드 를 눌 러 넣 은 다음 에 스 택 을 치기 시작 한 다음 에 현재 노드 의 오른쪽 노드 에 눌 러 넣 은 다음 에 왼쪽 노드 를 누 릅 니 다. 먼저 들 어간 후에 나 오 니까 오른쪽 노드 가 먼저 들 어가 면 나중에 인쇄 합 니 다.
public void pre(TreeNode root){
if (root == null) return;
Stack<TreeNode> stack=new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode curNode = stack.pop();
System.out.print(curNode.val+" ");//
if(curNode.right!=null) stack.push(curNode.right);
if(curNode.left!=null) stack.push(curNode.left);
}
}
중간 순서: 또한 하나의 스 택 을 사용 합 니 다. 먼저 나무의 왼쪽 노드 를 모두 눌 러 넣 고 왼쪽 노드 를 누 르 면 현재 노드 가 팝 업 되 기 시작 합 니 다. 그 다음 에 인쇄 를 처리 하고 현재 노드 가 그의 오른쪽 노드 를 가리 키 며 계속 순환 합 니 다. 만약 에 현재 노드 가 null 이면 스 택 을 누 르 지 못 하고 스 택 을 계속 나 갑 니 다.
public void mid(TreeNode root){
if (root == null) return;
Stack<TreeNode> stack=new Stack<>();
while (!stack.isEmpty() || root!=null){
// Null，
if(root !=null){
stack.push(root);
root=root.left;//
} else {
root = stack.pop();
System.out.print(root.val+" ");//
root=root.right;//
}
}
}
후 순 옮 겨 다 니 기: 두 개의 스 택 을 사용 합 니 다.stack 은 먼저 루트 노드 를 누 른 다음 팝 업 을 시작 합 니 다. 팝 업 후 현재 노드 를 stackNode 스 택 에 넣 습 니 다.현재 노드 에 왼쪽 노드 가 있 으 면 왼쪽 노드 를 누 르 고 오른쪽 노드 가 있 으 면 오른쪽 노드 를 누른다.마지막 으로 stackNode 스 택 을 인쇄 하 는 것 은 뒷 순 서 를 옮 겨 다 니 는 순서 입 니 다.
public void after(TreeNode root){
if (root == null) return;
Stack<TreeNode> stack=new Stack<>();
Stack<TreeNode> stackNode=new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode curNode = stack.pop();
stackNode.push(curNode);
if(curNode.left!=null) stack.push(curNode.left);
if(curNode.right!=null) stack.push(curNode.right);
}
while (!stackNode.isEmpty())
System.out.print(stackNode.pop().val+" ");
}
3. 차원 옮 겨 다 니 기
실현 절차: 1. 대기 열 을 만 들 고 각 층 의 노드 를 저장 합 니 다.2. 순환 을 사용 하여 대기 열 에서 결점 을 팝 업 합 니 다. 2.1 현재 결점 의 key 를 가 져 옵 니 다.2.2 현재 결점 의 왼쪽 결점 이 비어 있 지 않 으 면 왼쪽 결점 을 대열 에 넣 습 니 다. 2.3 현재 결점 의 오른쪽 결점 이 비어 있 지 않 으 면 오른쪽 결점 을 대열 에 넣 습 니 다.
public Queue<Integer> layerErgodic(){
Queue<Integer> values=new ArrayDeque<>();
ArrayDeque<TreeNode> queue=new ArrayDeque<TreeNode>();
queue.add(root);//
while (!queue.isEmpty()){
// ， ， ， values
TreeNode node = queue.remove();
values.add(node.val);
if(node.left!=null) queue.add(node.left);
if(node.right!=null) queue.add(node.right);
}
return values;
}
단계 판 옮 겨 다 니 기: 단계 에 따라 요 소 를 입력 하 십시오:
public List<List<Integer>> levelOrder(TreeNode root) {
if(root==null) return new ArrayList<>();
ArrayDeque<TreeNode> queue=new ArrayDeque<TreeNode>();
queue.add(root);
List<List<Integer>> lists=new ArrayList<>();
while (!queue.isEmpty()){
List<Integer> layer=new ArrayList<>();
// ， ， ， layer
int count=queue.size();//
while (count>0){
TreeNode node = queue.poll();
layer.add(node.val);
if(node.left!=null) queue.add(node.left);
if(node.right!=null) queue.add(node.right);
count--;
}
lists.add(layer);
}
return lists;
}
4. 나무의 최대 깊이
실현 절차: 1. 뿌리 결점 이 비어 있 으 면 최대 깊이 는 0 이다.2. 왼쪽 나무의 최대 깊이 계산 하기;3. 오른쪽 나무의 최대 깊이 계산 하기;4. 현재 나무의 최대 깊이 = 왼쪽 나무의 최대 깊이 와 오른쪽 나무의 최대 깊이 중 큰 자 + 1
private int maxDepth(TreeNode node) {
if(node==null) return 0;//1. ， 0；
int max=0;
int leftMax=0;
int rightMax=0;
if(node.left!=null) leftMax=maxDepth(node.left);
if(node.right!=null) rightMax=maxDepth(node.right);
//4. = +1
max=leftMax>rightMax? leftMax+1:rightMax+1;
return max;
}
2. 이 진 트 리 의 최대 너비
나무의 최대 너비
사상: 두 개의 대기 열 로 하나의 대기 열 에 노드 를 저장 하고 하나의 대기 열 에 해당 하 는 색인 위 치 를 저장 한 다음 각 층 의 최대 폭 은 대기 열 마지막 요소 (이 층 의 최대 노드) 색인 - 이 층 대기 열의 맨 앞 요소 색인 + 1 입 니 다.
class Solution {
public int widthOfBinaryTree(TreeNode root) {
if(root==null) return 0;
LinkedList<TreeNode> queue=new LinkedList<TreeNode>();
LinkedList<Integer> indexQueue =new LinkedList<Integer>();
queue.add(root);
indexQueue.add(1);
int maxWidth=1;
// ， ，
while (!queue.isEmpty()){
int count=queue.size();//
int left=indexQueue.peek();// ，
//
while (count>0){
TreeNode node = queue.poll();//
Integer index = indexQueue.poll();//
if(node.left != null){
queue.add(node.left);
indexQueue.add(index * 2);// 2*k
}
if (node.right != null) {
queue.add(node.right);
indexQueue.add(index * 2 + 1);// 2*k+1
}
count--;
if(count==0)
maxWidth = Math.max(maxWidth, index - left + 1); // ( - +1)
}
}
return maxWidth;
}
}
3. 이 진 트 리 인지 아 닌 지 판단
두 갈래 검색 트 리 판단: 두 갈래 검색 트 리 의 특징: 왼쪽 노드 가 오른쪽 노드 보다 작 습 니 다.중간 순 서 를 사용 하여 옮 겨 다 닐 수 있 습 니 다. 중간 순 서 는 절대적 으로 증가 합 니 다.
//
long preValue= Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if(root==null) return true;
boolean left=isValidBST(root.left);
boolean mid = false;
if(root.val>preValue) {
mid=true;
preValue=root.val;
}
boolean right= isValidBST(root.right);
return left && mid && right;
}
4. 밸 런 스 이 진 트 리 인지 판단
균형 이 진 트 리: 이 진 트 리 의 각 노드 의 좌우 두 개의 나무의 높이 차 이 는 절대 1 을 초과 하지 않 습 니 다.
사상: 후 서 를 옮 겨 다 니 며 현재 옮 겨 다 니 는 노드 에 대해 먼저 좌우 서브 트 리 의 균형 여 부 를 재 귀적 으로 판단 한 다음 에 현재 노드 를 뿌리 로 하 는 서브 트 리 의 균형 여 부 를 판단 한다.한 그루 의 나무 가 균형 이 잡 히 면 높이 (높이 는 반드시 마이너스 정수) 로 돌아 가 고 그렇지 않 으 면 - 1 로 돌아 갑 니 다.한 그루 의 나무 가 불 균형 하 다 면, 이 진 트 리 전체 가 불 균형 할 것 이다.
public boolean isBalanced(TreeNode root) {
if(root == null) return true;//
return getMaxHeight(root)>=0;
}
public int getMaxHeight(TreeNode node){
if(node==null) return 0;//
int leftHeight=0,rightHeight=0;
if(node.left != null)
leftHeight=getMaxHeight(node.left);//
if(node.right != null)
rightHeight=getMaxHeight(node.right);//
// -1 -1 1， -1
if(leftHeight == -1 || rightHeight==-1 ||Math.abs(leftHeight-rightHeight)>1)
return -1;
//
return leftHeight > rightHeight ? leftHeight+1:rightHeight+1;
}
5. 이 진 트 리 의 최근 공공 조상 (포인트)
두 노드 의 최근 공공 조상:
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// ， ，
if(root == null || root==p || root==q) return root;
TreeNode left=lowestCommonAncestor(root.left,p,q);//
TreeNode right=lowestCommonAncestor(root.right,p,q);//
//
// ， ， null， ，
if(left !=null && right !=null)
return root;
// ， null
return left!=null ? left:right;
}
6. 이 진 트 리 의 다음 노드 검색
다음 노드: 이 노드 의 후계 노드 란 중간 순서 로 옮 겨 다 니 는 것 입 니 다. p 보다 큰 다음 노드 입 니 다.
사상: 만약 에 p 가 현재 노드 의 값 보다 크 면 후계 노드 가 반드시 오른쪽 서브 트 리 에 있다 는 것 을 의미한다.
만약 에 p 가 현재 노드 의 값 보다 작 으 면 후계 노드 가 반드시 왼쪽 서브 트 리 나 자신 이 바로 왼쪽 서브 트 리 를 재 귀적 으로 호출 하고 비어 있 으 면 현재 노드 가 답 이라는 것 을 설명 한다.비어 있 지 않 으 면 왼쪽 나무 에서 적당 한 답 을 찾 았 다 는 뜻 으로 바로 돌아 가면 된다.
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
if(root == null) return null;
// ，
if (p.val >= root.val)
return inorderSuccessor(root.right, p);
// ，
// ，
TreeNode node = inorderSuccessor(root.left, p);
return node == null ? root : node;
}
7. 다른 나무의 자목
하위 트 리 인지 아 닌 지 판단 하기: 한 나무 가 다른 나무의 하위 트 리 라면 세 가지 상황:
// dfs isSameTree
public boolean isSubtree(TreeNode s, TreeNode t) {
// s 。 。 false
if (s==null) return false;
boolean sameFlag=isSameTree(s,t);//
boolean leftSubtree=isSubtree(s.left,t);//
boolean rightSubTree=isSubtree(s.right,t);//
return sameFlag || leftSubtree || rightSubTree;//
}
public boolean isSameTree(TreeNode s,TreeNode t){
if (s==null && t == null) return true; // ，
if (s == null || t == null) return false; // （ ）
//
// -- --
if (s.val != t.val) return false;// false
//
boolean left=isSameTree(s.left,t.left);
boolean right=isSameTree(s.right,t.right);
return left && right;
}
8. 이 진 트 리 재건
이 진 트 리 재 구축: 이 진 트 리 의 앞 순 서 를 옮 겨 다 니 며 중간 순 서 를 옮 겨 다 니 는 결과 에 따라 이 이 진 트 리 를 재 구축 합 니 다.입력 한 앞 순서 와 중간 순 서 를 옮 겨 다 니 는 결과 에 중복 되 는 숫자 가 없다 고 가정 합 니 다.
앞 순 서 를 옮 겨 다 니 는 첫 번 째 값 은 뿌리 노드 의 값 입 니 다. 이 값 을 사용 하여 중간 순 서 를 옮 겨 다 니 는 결 과 를 두 부분 으로 나 누고 왼쪽 부분 은 나무의 왼쪽 하위 트 리 에서 순서대로 옮 겨 다 니 는 결과 입 니 다. 오른쪽 부분 은 나무의 오른쪽 하위 트 리 에서 순서대로 옮 겨 다 니 는 결과 입 니 다.그리고 좌우 나무 에 대해 각각 재 귀적 으로 답 을 구한다.
//
private Map<Integer, Integer> indexForInOrders = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
for (int i = 0; i < inorder.length; i++)
indexForInOrders.put(inorder[i], i);
//
return getTree(preorder, 0, preorder.length - 1, 0);
}
private TreeNode getTree(int[] pre, int left, int right, int inL) {
if (left > right)
return null;
TreeNode root = new TreeNode(pre[left]);
int inIndex = indexForInOrders.get(root.val);
int leftTreeSize = inIndex - inL;
root.left = getTree(pre, left + 1, left + leftTreeSize, inL);
root.right = getTree(pre, left + leftTreeSize + 1, right, inL + leftTreeSize + 1);
return root;
}
9. 이 진 트 리 의 거울 (포인트)
두 갈래 나무의 거울
public TreeNode mirrorTree(TreeNode root) {
if(root == null) return null;
// （ ） 。
TreeNode tmpNode = root.left;
root.left=mirrorTree(root.right);
root.right=mirrorTree(tmpNode);
return root;
}
10. 이 진 트 리 의 대칭 여부
이 진 트 리 대칭 여부
public boolean isSymmetric(TreeNode root) {
if(root == null) return false;
return getIsSymmetric(root.left,root.right);
}
public static boolean getIsSymmetric(TreeNode tree1, TreeNode tree2) {
// true
if(tree1 == null && tree2==null) return false;
// false
if(tree1 == null || tree2 ==null) return false;
// false
if(tree1.val != tree2.val) return false;
// ，
return getIsSymmetric(tree1.left,tree2.right) && getIsSymmetric(tree1.right,tree2.left);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[JAVA] 배열 회전 출력요소 가 출력 을 시작 하 는 위치 에 주의 하 십시오. 모두 몇 라운드 의 수출 이 있 습 니까? n/2 + 1 매 라 운 드 는 상, 우, 하, 좌 로 나 뉜 다. 각 방향의 시작 위치 와 좌표 의 관 계 를 구...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
