描述

513. 找树左下角的值 - 力扣（Leetcode）

分析

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
import java.util.LinkedList;
import java.util.Queue;

//513.找树左下角的值
public class FindBottomLeftTreeValue513 {
	public static void main(String[] args){
		TreeNode root = createBT(new Integer[]{1,2,3,4,null,5,6,null,null,null,null,7});
		System.out.println("res = " + new Solution().findBottomLeftValue(root));
		show(root);
	}

	public static void show(TreeNode root) {
		System.out.println("二叉树层序遍历：");
		Queue<TreeNode> queue = new LinkedList<>();
		queue.offer(root);
		
		while(!queue.isEmpty()){
			int size = queue.size();
			TreeNode temp;
			for (int i = 0; i < size; i++) {
				temp = queue.poll();
				System.out.print(temp.val + "\t");
				if (temp.left != null) queue.offer(temp.left);
				if (temp.right != null) queue.offer(temp.right);  
			}
			System.out.println();
		}
    }
    public static TreeNode createBT(Integer[] arr){
	    if(arr.length == 0){
	        return null;
	    }
	    TreeNode root = new TreeNode(arr[0]);
	    Queue<TreeNode> queue = new LinkedList<>();
	    queue.add(root);

	    boolean isLeft = true;//是左子树
	    for(int i = 1; i< arr.length; i++){
	        TreeNode node = queue.peek(); //peek()获取第一个元素，不移除
	        if(isLeft){
	            if(arr[i] != null){
	                node.left = new TreeNode(arr[i]);
	                queue.offer(node.left); //offer(E e) 在队列尾部添加一个元素，并返回是否成功
	            }
	            isLeft = false;
	        } else {
	            if(arr[i] != null){
	                node.right = new TreeNode(arr[i]);
	                queue.offer(node.right);
	            }
	            //右节点加入队列尾部，删除第一个元素，保证队列里保存的是根节点
	            queue.poll(); //poll()  删除队列中第一个元素，并返回该元素的值,
	            isLeft = true;
	        }
	    }
	    return root;
	}
}
//递归
class Solution1 {
	//最后的返回值
    private int value = 0;
    //找节点的深度
    private int Deep = -1;

    public int findBottomLeftValue(TreeNode root) {
    	value = root.val;
    	findLeftValue(root, 0);
    	return value;
    }

    //root:根节点 deep：深度
    private void findLeftValue(TreeNode root, int deep){
    	//root 为null
    	if(root == null) return;
    	//root 为 叶子节点
    	if(root.left == null & root.right == null) {
    		//如果这个叶子节点的比之前的result深
    		if (deep > Deep) {
    			//deep 和返回值 value都改一下
    			value = root.val;
    			Deep = deep;
    		}
    	}
    	//root 为非叶子节点
    	if (root.left != null) findLeftValue(root.left,deep + 1);
    	if (root.right != null) findLeftValue(root.right,deep + 1);
    }
}
//迭代
class Solution {
	public int findBottomLeftValue(TreeNode root) {
		int res = 0;
		Queue<TreeNode> queue = new LinkedList<>();
		queue.offer(root);
		
		while(!queue.isEmpty()){
			int size = queue.size();
			TreeNode temp;
			for (int i = 0; i < size; i++) {
				temp = queue.poll();
				//处理一行最左边那个值
				if (i == 0) res = temp.val;
				if (temp.left != null) queue.offer(temp.left);
				if (temp.right != null) queue.offer(temp.right);  
			}
		}
		return res;
    }
}

class TreeNode {
    int val;
   	TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
        this.left = left;
        this.right = right;
    }
 }

总结

在这个【一维数组构建二叉树】这里吃了亏。

这个专门写了一篇，Ctrl + F 关键字就能找到